Exercise XI

You are the CEO of a startup software company. The app your company is building requires a component that performs an image processing task. Your intern is told to survey the literature for potential solutions to this computational task. Upon studying the literature, the intern finds three algorithms that solve the problem at hand. The algorithms have the following runtimes: $O(\lg n)$, $O(2^n)$, and $O(n)$.

Exercise Which algorithm will you choose to be implemented?

A) The one with $O(n)$ runtime.
B) The one with $O(2^n)$ runtime.
C) The one with $O(\lg n)$ runtime.

Solution

You are a true engineer if you answer that you need more information! (Such as the resources required to implement/run each algorithm, their tradeoffs other than their runtime, etc.)

If you told your intern the runtime of these algorithms could all be the same, then you truly understood the mathematical definition of Big-Oh (more on this later!) and now trying to show off!! (Or you are Sheldon Cooper from the Big Bang Theory! In either case, my heart goes out to the poor intern!)

If you said let's go with the one with $O(\lg n)$ runtime, then you understood the growth rate of functions and the use of Big-Oh notion in conversational language that computer scientists use to describe how fast algorithms run.

Let's focus on that last case (we will revisit this question later!).

The $\lg n$ grows slower than $n$, and they both grow much slower than $2^n$, as $n$ gets arbitrarily large.

So an algorithm with runtime proportional to $\lg n$ is faster than one with runtime proportional to $n$. Moreover, they both are much quicker than one with runtime proportional to $2^n$, when the input size, $n$, gets arbitrarily large.