Is there any algorithm whose big O and big theta are different?

Question

Is there any algorithm whose big O and big theta are different? I found them to be quite similar and confusing at the same time.

Answer 1

I think that part of the confusion here stems from the fact that algorithms don't have "a big-O" or "a big-Theta." O and Θ notation are used to describe the long-term growth rates of functions, rather than algorithms. When you hear someone say something like "binary search is O(log n)," what they're really saying is "the runtime of binary search is O(log n)" or "the worst-case runtime of binary search on an input of length n is O(log n)."

The other reason that this can be confusing is that one function can be big-O of a number of different functions. For example, the function f(n) = n is O(n), but it's also O(n²), O(n³), O(2ⁿ), etc. This stems from the formal definition of big-O notation, which says that f(n) = O(g(n)) if (intuitively) in the long term f(n) is bounded from above by some constant multiple of g(n). This means that we can't necessarily speak of "the" big-O of some function's runtime, since there can be infinitely many functions that might fit the bill.

What we can say is the following: if a function's runtime is Θ(f(n)), then the function's runtime is also O(f(n)). This follows from the definition of Θ notation. On the other hand, the converse isn't necessarily true; if a function has runtime O(f(n)), it's not necessarily the case that the function's runtime is Θ(f(n)). We can use something like binary search as an example - binary search runs in time O(log n), but its runtime is also O(n) and O(n²) because those are weaker bounds. However, the runtime of binary search is not Θ(n), nor is it Θ(n²) or Θ(2ⁿ).

Answer 2

You can think about big O as an asymptotic upper bound. And there is a big Omega for an asymptotic lower bound.

If big O and big Omega is identical it is in big Theta.

For example you can think about an algorithm to find the biggest number in an unordered sequence of length n. The algorithm is very simple it checks number for number and stores the current max value in a variable. In the worst case you have to check every value in the sequence (it is unordered and the biggest value is at the end) so big Omega = n. Now you can think about an upper bound, and it could be also n. But for example n squared is also an valid upper bound or n! etc.