Big-O and repeated trials

When you compare algorithms, what matters is how the cost grows as the input grows, not the exact count. Big-O notation says this briefly: $f(n) = O(g(n))$ means that $f$ grows no faster than $g$, ignoring constant factors. Precisely, there is a constant $C$ with $f(n) \le C\,g(n)$ for every large enough $n$.

For example, $3n^2 + 5n = O(n^2)$: once $n \ge 5$, $5n \le n^2$, so $3n^2 + 5n \le 4n^2$. Constant factors and smaller terms drop out. Big-O is only an upper bound, so $n = O(n^2)$ is true as well; it just says less than $n = O(n)$. When people quote a cost such as $O(n^2)$, they mean the smallest simple class that fits.

Five functions come up again and again in this course: $\log_2 n$, $\sqrt n$, $n$, $n^2$ and $2^n$. Each one eventually leaves the one before it far behind. Here they are at a few sizes, rounded:

Watch which variable a cost is measured in. Grover search, in Part 2, takes about $\sqrt N$ steps to search $N$ items. If the items are labelled by $n$⁠-bit strings, then $N = 2^n$ and

That is still exponential in the number of bits $n$, only with half the exponent. A square-root speedup of an exponential cost leaves an exponential cost. It is a real gain, since $2^{n/2}$ is far smaller than $2^n$, but it does not turn an exponential problem into a polynomial one.

A cost that grows like a power of the input size, such as $n$, $n^2$ or $n^{10}$, is called polynomial. A cost that grows like $2^n$ or $2^{n/2}$ is exponential. Polynomial-time algorithms count as efficient.

The difference shows when hardware improves. Suppose a computer becomes 1000 times faster. For an algorithm whose time grows like $n^2$, the largest input you can handle in the same time grows by a factor $\sqrt{1000} \approx 31.6$. For one whose time grows like $2^n$, it grows by $\log_2 1000 \approx 10$: ten more bits, however large $n$ already was. No faster machine fixes an exponential cost, which is why turning an exponential cost into a polynomial one is the prize.

Many algorithms succeed only with some probability $p$ per run, but you can check whether a run succeeded, for example by testing the answer it gives. Then you repeat until a run succeeds. All of $k$ independent runs fail with probability $(1-p)^k$, and since $1 - p \le e^{-p}$,

To push the chance of failure below $\delta$, it is enough that $e^{-pk} \le \delta$, that is $k \ge \ln(1/\delta)/p$. So about $\ln(1/\delta)/p$ runs suffice. The dependence on $\delta$ is only logarithmic: going from a failure chance of one in a thousand to one in a million just doubles the number of runs, since $\ln 10^6 = 2\ln 10^3$.

Some algorithms give an answer that is right with probability at least $\tfrac23$, and you can’t check the answer directly. Run such an algorithm $k$ times, with $k$ odd, and take the majority answer. The majority is wrong only if more than half the runs are wrong, and that becomes unlikely fast. A result called the Chernoff bound shows that the chance falls off exponentially in $k$, roughly like $e^{-ck}$ for a constant $c$ that depends on how far the success chance is above $\tfrac12$.

In the majority-vote chart above, three runs give a wrong majority with probability $\tfrac{7}{27} \approx 0.26$, and 21 runs with probability about $0.06$. Any fixed success chance above $\tfrac12$ can be pushed close to certainty with a modest number of runs. That is why “right with probability $\tfrac23$” is the usual standard for a randomized algorithm: the $\tfrac23$ itself is arbitrary.