Disambiguating Big-O and Theta for Expressing Time Complexity

Can someone please give me an example of two algorithms, one where "Big-O" is the most appropriate expression of how time complexity grows with input size, and one where this would be Θ?

Can you please be very clear about whether the statements refer to best, average or worst case, and about implicit assumptions about the input or anything else, beyond the fact that the general approach is to consider how the number of basic operations in a hypothetical machine grows with input size.

Lets start by explaining the difference between big-O and $$\Theta$$. Basically, if we think of big-O as "bounding from above", we can think of $$\Theta$$ as "bounding both from below and from above". Formally, $$f=\Theta(g)\iff f=O(g)\land f=\Omega(g)$$. This $$f=\Omega(g)$$ means that $$g$$ bounds $$f$$ from below, and is equivalent to saying that $$g=O(f)$$ ($$g$$ bounds $$f$$ from below if $$f$$ bounds $$g$$ from above).

So basically, $$f=O(g)$$ means that $$f$$ is asymptomatically at most like $$g$$, but $$f=\Theta(g)$$ means that $$f$$ is asymptomatically equivalent to $$g$$.

In the context of algorithms, the notions are a bit abused. For example, one may write "this algorithm works in $$O(n)$$", when he/she really meant "this algorithm runs in $$\Theta(n)$$".

Most of the times, this doesn't make a big difference. But sometimes, especially with algorithms that are hard to analyze - this distinction is important. Since those algorithms are hard to analyze, its perfectly possible that the proven run-time bounds are not tight, which means they are not $$\Theta$$ but are just $$O$$.

On the other hand, when someone explicitly writes $$\Theta$$, it probably means either one of two things (depending on the context, check it carefully!):

1. The algorithm's proven bound for the run-time is tight
2. This algorithm was proven to achieve a run-time equal to the known lower bound pf the problem. For example, with sorting - there is a nice proof that no comparison-based algorithm can sort in less than $$n\log(n)$$ time - this is a lower bound. Now, mergesort runs in $$O(n\log(n))$$, and hence it is optimal since it achieves the lower bound. So one may say that mergesort works in $$\Theta(n\log(n))$$.
• When talking about algorithms 2 implies 1 so I would argue it always means 1 (and if I read "algorithm $A$ runs in $\Theta(n^2)$ time" I wouldn't assume that there is a matching lower bound on the problem just because of the use of $\Theta$). The meaning number 2 is more when talking about a problem than an algorithm (something like "the complexity of sorting in a comparison based model is $\Theta(n\log n)$"). It would be sloppy to mix the two imho. Oct 20 '21 at 11:19
• $f = O(g)$ means that $f$ is asymptotically at most $g$. Oct 20 '21 at 12:52

Asymptotic notation arose in number theory, and is now commonly used in combinatorics. It has nothing to do with algorithms per se. We use asymptotic notation to describe the resource consumption of algorithms, mainly time and space. It comes in five main flavors:

• $$f(n) = O(g(n))$$ if $$f(n) \leq Cg(n)$$ for some constant $$C>0$$. In words, $$f(n)$$ grows at most as fast as $$g(n)$$.
• $$f(n) = \Omega(g(n))$$ if $$f(n) \geq cg(n)$$ for some constant $$c>0$$. In words, $$f(n)$$ grows at least as fast as $$g(n)$$.
• $$f(n) = \Theta(g(n))$$ if $$cg(n) \leq f(n) \leq Cg(n)$$ for some constants $$C,c>0$$. In words, $$f(n)$$ and $$g(n)$$ grow at the same rate.
• $$f(n) = o(g(n))$$ if $$\lim_{n\to\infty} f(n)/g(n) = 0$$. In words, $$f(n)$$ grows slower than $$g(n)$$.
• $$f(n) = \omega(g(n))$$ if $$\lim_{n\to\infty} f(n)/g(n) = \infty$$. In words, $$f(n)$$ grows faster than $$g(n)$$.

When we say that an algorithm runs in time $$O(f(n))$$, we mean that its running time is bounded by $$Cf(n)$$, for some constant $$C > 0$$. Often there is an unstated assumption that the bound is tight, that is, the function $$f(n)$$ cannot be replaced by any asymptotically smaller function. However, strictly speaking, this is not the meaning of $$O(f(n))$$. For example, quicksort runs in time $$O(n!)$$. This is a pretty bad bound, but the statement is mathematically valid nonetheless.

What do we mean when we say that an algorithm runs in time $$\Theta(f(n))$$? Strictly speaking, this means that the running time of the algorithm is always between $$cf(n)$$ and $$Cf(n)$$, for some constants $$C,c>0$$. However, sometimes this kind of bound is too much to hope for, since the running time could depend on the particular input, or if the algorithm is randomized, on the random coin tosses. For example, quicksort always runs in $$O(n^2)$$, but sometimes it runs in $$O(n\log n)$$. We can say that its worst-case complexity is $$\Theta(n^2)$$, but it is not true that its runtime is $$\Theta(n^2)$$.

When should you use which notation? That's up to you. If you can bound the quantity in question tightly, then you might as well use big Theta. If all you have is an upper bound, you should use big O. If you know the worst-case complexity but want to describe the "every-case" complexity, the convention is to use big O, with the tacit understanding that the bound is probably tight for the worst case.