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).

Data Structures

Exercise XII