6
$\begingroup$

What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?

$\endgroup$
9
$\begingroup$

First of all, when people talk about big O complexity, they refer to the complexity of an algorithm, usually its running time. A somewhat better term is big O asymptotics. Big O makes sense to functions beyond the running time of an algorithm, indeed beyond any kind of complexity measure of an algorithm. Big O notation actually first appeared in the context of number theory, where it is used to simplify many statements.

Now back to your question. There really isn't any such thing as the big O complexity of a function. Let us take as an example your function. It has many big O estimates, such as:

  • $9n^2 + 10n = O(9n^2 + 10n)$.
  • $9n^2 + 10n = O(n^2)$.
  • $9n^2 + 10n = O(n^3)$.

The first two estimates are better than the third one, since they are tight: not only do we have $9n^2 + 10n = O(9n^2 + 10n)$, but in fact $9n^2 + 10n = \Omega(9n^2 + 10n)$, whereas it is not true that $9n^2 + 10n = \Omega(n^3)$. Comparing the first two estimates, the second one is better since it is simpler.

What does simple mean? Although this is an informal notion, everybody will agree that functions of the form $a^n n^k \log^\ell n$ are simple. If we fix this class of simple functions, then the unique simple function $f(n)$ such that $9n^2 + 10n = O(f(n))$ and moreover this is a tight bound is $f(n) = n^2$ (i.e., $a=1$, $k=2$, $\ell=0$). This could be termed "the" big O asymptotics of $9n^2 + 10n$, but a much better term would be the big $\Theta$ asymptotics of $9n^2 + 10n$, since the statement $9n^2 + 10n = \Theta(n^2)$ encompasses the property that this a tight upper bound.

This discussion suggests that when you are given an explicit function, you shouldn't be looking for big O and big $\Omega$ estimates – instead, you should aim higher, at a simple big $\Theta$ estimate.

The true role of big O and big $\Omega$ is in other situations. One situation is when analyzing the running time of an algorithm. The exact running time could depend on the input in a complicated way. For example, when running binary search on an array of length $n$, the algorithm could terminate after one step, two steps, or more – but always within $O(\log n)$ steps. We cannot describe the running time using big $\Theta$, since the best lower bound $\Omega(1)$ and the best upper bound $O(\log n)$ do not match. The same cannot be said about your example.

Another situation in which it makes sense to use big O and big Omega is when it is hard to find the exact asymptotics of a function. Take as an example the central binomial coefficient $\binom{2n}{n}$. Since $\sum_{m=0}^{2n} \binom{2n}{m} = 4^n$ and since $$\binom{2n}{0} < \binom{2n}{1} < \cdots < \binom{2n}{n-1} < \binom{2n}{n} > \binom{2n}{n+1} > \cdots > \binom{2n}{2n-1} > \binom{2n}{2n}, $$ we can obtain the following upper and lower bounds: $$ \frac{4^n}{2n+1} \leq \binom{2n}{n} \leq 4^n. $$ This shows that $\binom{2n}{n} = O(4^n)$ and $\binom{2n}{n} = \Omega(4^n/n)$, where in both cases we are using simple functions as our estimators. The true rate of growth is $\binom{2n}{n} = \Theta(4^n/\sqrt{n})$, but this is harder to establish. In more complicated cases, it could be hard to find the exact rate of growth, or perhaps we are content with only an upper bound or only a lower bound, and then it makes sense to use big O or big $\Omega$.

One could also come up with contrived examples, which rarely happen in practice, in which there is no simple big $\Theta$ estimate for a given function. For example, consider the function $$ f(n) = \begin{cases} n & \text{ if $n$ is even}, \\ n^2 & \text{ if $n$ is odd}. \end{cases} $$ The best simple lower bound one could give is $f(n) = \Omega(n)$, and the best simple upper bound is $f(n) = O(n^2)$, but the two don't match.

Finally, while in analyzing algorithms we usually don't care about multiplicative constants, since they depend on details which our analysis abstracts away on purpose, in other situations it makes sense to ask for information beyond big Theta. For example, we can get an asymptotic estimate of the form $$ \binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}. $$ Or we could ask for an asymptotic series, such as $$ \binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} - \frac{4^n}{8\sqrt{\pi} n^{3/2}} + O\left(\frac{4^n}{n^{5/2}}\right). $$

At this point in your training, however, it's probably better to concentrate at the more elementary stuff, which is of more widespread use in computer science.

$\endgroup$

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.