Comparing Growth Rates

Intuition by Algorithmic Pattern

Growth rate	Typical algorithm pattern
$O(1)$	Array access, arithmetic, hash table lookup
$O(\log n)$	Binary search, balanced BST operations, divide-and-conquer depth
$O(n)$	Linear scan, counting sort, merging two sorted lists
$O(n \log n)$	MergeSort, HeapSort, QuickSort average case, FFT
$O(n^2)$	Insertion Sort, nested pairwise loops, naive matrix multiplication
$O(n^3)$	Triple-nested loops, Floyd-Warshall all-pairs shortest path
$O(2^n)$	Brute-force subset enumeration, naive recursion for Fibonacci
$O(n!)$	Brute-force permutation enumeration, travelling salesman (naive)

Concrete Numbers

For a machine doing $10^9$ operations per second:

$n$	$\log_2 n$	$n$	$n \log_2 n$	$n^2$	$n^3$	$2^n$
10	3.3	10 ns	33 ns	100 ns	1 µs	1 µs
100	6.6	100 ns	660 ns	10 µs	1 ms	$4 \times 10^{13}$ years
1,000	10	1 µs	10 µs	1 ms	1 s	astronomically large
$10^6$	20	1 ms	20 ms	17 min	32,000 years	impossible
$10^9$	30	1 s	30 s	32,000 years	impossible	impossible

A supercomputer running at $10^{15}$ ops/sec would handle $n=10^6$ with Insertion Sort ($n^2$) in about 1 second, and MergeSort ($n \log n$) instantly. The algorithm matters far more than the hardware.

Using Limits to Compare Growth

To determine the asymptotic relationship between $f(n)$ and $g(n)$, compute:

$\lim_{n \to \infty} \frac{f(n)}{g(n)}$

Limit	Conclusion
0	$f(n) = o(g(n))$, so $f(n) = O(g(n))$ but not $\Theta(g(n))$
$c \in (0, \infty)$	$f(n) = \Theta(g(n))$
$\infty$	$f(n) = \omega(g(n))$, so $f(n) = \Omega(g(n))$ but not $\Theta(g(n))$

Example: Compare $n \log n$ and $n^2$

$\lim_{n \to \infty} \frac{n \log n}{n^2} = \lim_{n \to \infty} \frac{\log n}{n} = 0 \quad \text{(by L'Hôpital)}$

So $n \log n = o(n^2)$; the $n^2$ function dominates.

Example: Compare $3n^2 + 2n + 1$ and $n^2$

$\lim_{n \to \infty} \frac{3n^2 + 2n + 1}{n^2} = 3$

The limit is finite and non-zero, so $3n^2 + 2n + 1 = \Theta(n^2)$.

L’Hôpital’s Rule

If $\lim f(n) = \lim g(n) = \infty$, then:

$\lim \frac{f(n)}{g(n)} = \lim \frac{f'(n)}{g'(n)}$

This is essential for ratios like $\frac{\log n}{n}$ or $\frac{n}{\log n}$ where the asymptotic behaviour is not obvious from inspection.

Practice: Rank by Growth Rate

Rank these functions from slowest to fastest growth:

$2^{\log_3 n}, \quad n^2, \quad \sqrt{n}, \quad \log(n!), \quad 2^n, \quad n^{\log 3}, \quad n \log n, \quad (\log n)^{\log n}$

Solution: $2^{\log_3 n} = n^{\log_3 2} \approx n^{0.63}$; $\log(n!) = \Theta(n \log n)$; $n^{\log 3} \approx n^{1.59}$. The rank: $\sqrt{n} < 2^{\log_3 n} < n \log n \approx \log(n!) < n^{\log 3} < n^2 < (\log n)^{\log n} < 2^n$.

Summary

Rate	Example algorithm	$n=10^6$ on 1 GHz
$\log n$	Binary search	20 ns
$n$	Linear scan	1 ms
$n \log n$	MergeSort	20 ms
$n^2$	Insertion Sort worst	17 min
$n^3$	Floyd-Warshall	32,000 years
$2^n$	Subset enumeration	impossible
Limit test	$\lim f/g$ determines $o$, $\Theta$, $\omega$