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 |