Deamortizing a Las-Vegas randomized algorithm
If the expected running time of the algorithm is $c'n$, then Markov's inequality shows that for all $A$, the probability that the algorithm takes more than $Ac'n$ operations is at most $1/A$. If you run $Ac'$ operations each time then you will finish computing with probability $1-1/A$, and if you run $Ac'$ operations each time until the last step, at which you let the algorithm loose, then the number of operations will be at most $Ac'$ with probability $1-1/A$.

In some cases you know more about the distribution of the running time of the algorithm – say its variance. In that case you can get better bounds using (for example) Chebyshev's inequality.

Another trick to try is to run several instances of the algorithm in parallel with fresh coins. For example, suppose that we run $B$ independent instances of the algorithm, each for $(A/B)c'$ operations at each step. The probability that none of them finishes is at most $(B/A)^B$, compared to $1/A$ we had before. Choosing $B \approx A/e$, this improves the failure probability from $1/A$ to roughly $e^{-A/e}$.