Algorithm time complexity analysis

Big O vs Big Omega vs Big Theta

Big O notation expresses the upper bound of an algorithm's time complexity and provides an estimate of how long the algorithm will take in the worst case scenario, based on input size.

Big Omega notation expresses the lower bound of an algorithm's time complexity. It tells us how long we can expect an algorithm to take in the best case scenario, in terms of the size of the input.

Big Theta notation expresses both the upper and lower bounds of an algorithm's time complexity, providing a tight estimate of how long the algorithm will take in all cases. It is used to describe the average case complexity of an algorithm.

In summary:

Big O is upper bound, worst case of an algorithm’s time performance.

$$f(n) ≤ cO(n), if \enspace n >= n_0$$

Big Omega is lower bound, best case of an algorithm’s time performance.

$$c*Omega(n) ≤ f(n), if\enspace n ≥ n_0$$

Big Theta is tight bound expressing both lower bound and upper bound of an algorithm’s time performance.

$$c_1* Theta(n) ≤ f(n) ≤ c_2*Theta(n), if \enspace n ≥ n_0$$

How to prove the Big O bound of a function or an equation?

1. Prove base case.
2. Assume it’s true for (n-1) or n.
3. Prove it’s true for n or (n+1).