Common order-of-growth classifications

order-of-growth-classifications.md

Common order-of-growth classifications

order of growth	name	code example	description	example	T(2N) / T(N)
1	constant	a = b + c	statement	add 3 numbers	1
log N	logarithmic	while (N > 1) { n = N / 2; }	divide in half	binary search	~ 1
N	linear	for (i = 0; i < N; i++) { /* ... */ }	loop	find the maximum	2
N log N	linearithmic	[mergesort]	divide and conquer	mergesort	~ 2
N^2	quadratic	for (i = 0; i < N; i++) for (j = 0; j < N; j++) { /* ... */ }	double loop	check all pairs	4
N^3	cubic	for (i = 0; i < N; i++) for (j = 0; j < N; j++) for (k = 0; k < N; k++) { /* ... */ }	triple loop	check all triples	8
2^N	exponential	[combinatorial search]	exhaustive search	check all subsets	T(N)