How Algorithms Scale

Double the input and a fast algorithm barely notices while a slow one takes forever. Comparing how functions grow tells you which code survives real data.

How it works

Logarithmic, polynomial and exponential growth

In one sentence

For large $n$ , $\log_2 n \ll n \ll n\log_2 n \ll n^2 \ll 2^n$ : each function eventually exceeds any constant multiple of those before it.

General formula

{\htmlData{sym=1}{\log_2 n}} \;{\htmlData{sym=4}{\ll}}\; {\htmlData{sym=5}{n}} \;{\htmlData{sym=4}{\ll}}\; {\htmlData{sym=0}{n\log_2 n}} \;{\htmlData{sym=4}{\ll}}\; {\htmlData{sym=2}{n^2}} \;{\htmlData{sym=4}{\ll}}\; {\htmlData{sym=3}{2^n}}

Doubling $n$ adds $1$ to $\log_2 n$ , doubles $n$ , quadruples $n^2$ and squares $2^n$ .

What the symbols mean

$n\log_2 n$
Linearithmic
Work for good sorting algorithms like merge sort.
$\log_2 n$
Logarithmic
Doubling the input adds just one step, as in binary search.
$n^2$
Quadratic
Doubling the input quadruples the work, as with nested loops.
$2^n$
Exponential
Each extra item doubles the work, as in brute-force search.
$\ll$
Much smaller than
For large inputs the left side grows far more slowly than the right.
$n$
Input size
How many items the algorithm has to process.

Binary search is $O(\log n)$ because every step halves what is left.
Comparing every pair of items is $O(n^2)$ .
Trying every subset is $O(2^n)$ , hopeless past a few dozen items.

Learn the math

Integer ExponentsAlgebra · Lesson 1, Preliminaries Exponential FunctionsAlgebra · Lesson 39, Exponential and Logarithm Functions Logarithm FunctionsAlgebra · Lesson 40, Exponential and Logarithm Functions Limits at Infinity: Exponentials and LogarithmsCalc I · Lesson 11, Limits L'Hôpital's Rule and Indeterminate FormsCalc I · Lesson 35, Applications of Derivatives The Integral TestCalc II · Lesson 29, Sequences and Series

Learn the math

Integer ExponentsAlgebra · Lesson 1, Preliminaries

Exponential FunctionsAlgebra · Lesson 39, Exponential and Logarithm Functions

Logarithm FunctionsAlgebra · Lesson 40, Exponential and Logarithm Functions

Limits at Infinity: Exponentials and LogarithmsCalc I · Lesson 11, Limits

L'Hôpital's Rule and Indeterminate FormsCalc I · Lesson 35, Applications of Derivatives

The Integral TestCalc II · Lesson 29, Sequences and Series