Let's say I have a Las Vegas algorithm $L$ for some problem $P$, which runs in $n^3$ steps with 50% likelihood. My friend asks me for an algorithm for $P$ that runs in $n^3$ steps with 75% likelihood. My intuition says, "No problem! I'll just run $L$ once, and if it doesn't return after $n^3$ steps, I'll terminate it. Then, I'll run it again. The likelihood that it fails to return after $n^3$ steps twice in a row is only 25%."

Is my intuition correct? I know that if it's running twice, that's technically $2n^3$ and that would be subsumed by big-O notation. Maybe the problem that was posed to me was not carefully worded enough...

  • 1
    $\begingroup$ Have you tried to prove your intuition? $\endgroup$ – Yuval Filmus Nov 12 '18 at 8:11
  • $\begingroup$ No I haven't. I don't really know if this is a valid way to think about the question. $\endgroup$ – data princess Nov 12 '18 at 14:29
  • $\begingroup$ @dataprincess You are allowed to create a new algorithm, and you can certainly use the existing one. Everything goes. $\endgroup$ – Raphael Nov 12 '18 at 22:44
  • $\begingroup$ "runs in $n^3$ steps with 50% likelihood" -- do you mean that the algorithm takes at most $n^3$ steps with probability $0.5$, and more steps otherwise? If not, you need to be more precise there. $\endgroup$ – Raphael Nov 12 '18 at 22:45
  • $\begingroup$ I mean that 50% of the time, it runs in $n^3$ steps, and the other 50% of the time, it takes longer. I can clarify the question. $\endgroup$ – data princess Nov 13 '18 at 1:44

Depends on what you mean by “better”. There is always a compromise between cost and the quality of the results. Accepting higher cost for higher quality does not make it a better algorithm in my book.

I would say that a “better” algorithm is one that produces equal quality at lower cost, or better quality at the same cost.

  • $\begingroup$ This addresses the title of my question, but I'm more curious about the specifics. It seems like this does produce better quality at the same cost, because it solves the problem with a tighter guarantee on running time. $\endgroup$ – data princess Nov 12 '18 at 14:28
  • $\begingroup$ Running it twice isn’t the same cost, it’s twice the cost. $\endgroup$ – gnasher729 Nov 12 '18 at 15:45
  • $\begingroup$ @gnasher729 The question is unclear about whether the algorithm is supposed to run in $n^3$ steps or $O(n^3)$ steps. If it's the latter, then twice the cost is "the same cost". $\endgroup$ – David Richerby Nov 12 '18 at 19:01

Monte Carlo and Las Vegas algorithms are equivalent and this question is more naturally asked in terms of the former so I will pretend you asked about Monte Carlo.

Any Monte Carlo algorithm can be run multiple (say, a constant number of) times to amplify the probability of success while slowing down the algorithm. And in fact you can achieve any fixed probability of success $< 1$ while slowing down by a constant factor.

Where you "cheat" is that you adopt the convention of ignoring the constant factor in run time while simultaneously caring about the constant probability of success. As the probability can be freely adjusted by multiplying run time by a constant, caring about its particular value is equivalent to caring about the constant factor in run time so big O is inappropriate in this situation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.