Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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!):
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:
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.
