CSC300 / CSC402: Order of growth [8/9] Previous pageContentsNext page

Name Function Intuition
Constant O(1) Data independent
Logarithmic O(lg(n)) Iteratively cut in half
Linear O(n) Iterate once for each item
Linearithmic O(n * lg(n)) Nested iteration: once linear, once logarithmic
Quadratic O(n^2) Nested iteration: twice linear
Cubic O(n^3) Nested iteration: three times linear
Exponential O(2^n) Combinations
Factorial O(n!) Permutations

big-o-running-time-complexity

Image from 8 time complexities that every programmer should know by Adrian Mejia

Previous pageContentsNext page