Exercise XII

  • Rank asymptotic complexities from smallest to largest.

Exercise Two alternative algorithms, $A$ and $B$, have logarithmic and linear runtimes, respectively. Which statement is true?

A) $A$'s runtime function grows faster thus $A$ is faster
B) $A$'s runtime function grows slower thus $A$ is faster
C) $B$'s runtime function grows faster thus $B$ is faster
D) $B$'s runtime function grows slower thus $B$ is faster

Solution

You can imagine A is binary search and B is linear search. Based on the information we have, A runs faster. How do we know that? Because $\lg n$ grows slower than $n$, as $n$ gets larger and larger, which means it takes less time for $A$ to do its work. So the answer is (B).