Exercise XI
You are the CEO of a startup software company. The app your company is building requires a component that performs some sort of image processing task. Your intern is told to survey the literature for potential solutions to this computational task. Upon surveying 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
If your answer is that you need more information, such as the resources required to implement/run each algorithm, their tradeoffs other than their runtime, etc, you are a true engineer!
If you told your intern the runtime of these algorithms can 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. (Congratulations... you are normal!)
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$, and they both are much faster than one with runtime proportional to $2^n$, when the input size, $n$, gets arbitrarily large.