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 of the binary search algorithm.

When we use Big-Oh/Omega to communicate how fast an algorithm is, we give the tightest upper/lower bound we can prove true.