Exercise IV

Exercise Which of the following are correct asymptotic runtime for the binary search algorithm? (There may be more than one correct answer!)

A) $O(n^2)$
B) $O(n)$
C) $O(\lg n)$
D) $\Omega(\lg n)$
E) $\Omega(1)$

Solution

All of the above!

Relying only on the formal definitions of big Oh and big Omega, it would be mathematically justified, but rather strange (and unhelpful) to use all of the above to describe the asymptotic running time the binary search algorithm.

When we uses big Oh/Omega to communicate how fast an algorithm is, we give the tightest upper/lower bound we can prove to be true.