Growth Rate and the Common Families

$$1\ll \log n\ll n\ll n\log n\ll n^2\ll n^3\ll 2^n\ll n!$$

Examples: swap or reading an element by index is $O(1)$; binary search is $O(\log n)$; linear search is $O(n)$; the fastest general-purpose sorts are $O(n\log n)$; selection sort is $O(n^2)$.

The first three are all $O(n)$. The fourth is $O(n^2)$.

$2n$, $n$, and $\frac{n}{2}$ differ by a constant factor, and that factor is the same at every $n$. The gap between $n$ and $n^2$ keeps growing as $n$ grows, with no bound. Big-Oh keeps the growth rate and drops the constant because the growth rate is what decides which algorithm does less work on large inputs.

$A$ is faster for large $n$, because $n$ grows more slowly than $n^2$.

$B$ does less work while $n^2<1000n$, that is, for every $n$ below $1000$. At $n=1000$ the two tie, and for every larger $n$, $A$ does less work.

The answer is (B).

Imagine $A$ is binary search and $B$ is linear search. $A$ is logarithmic and as $n$ grows, $\log n$ grows more slowly than $n$. So $A$’s runtime grows more slowly than $B$’s. The algorithm in the slower-growing family does less work as $n$ gets large, so $A$ finishes sooner; it is the faster algorithm.