Algorithms
What Is Big O Notation?
Also called: Time complexity
Big O notation describes how an algorithm’s running time or memory grows as its input grows, ignoring constants and smaller terms.
Definition
Big O notation is a way to say how much slower an algorithm gets as its input gets bigger. It describes the growth rate, not the exact time in seconds, so the result does not depend on the computer.
It usually describes the worst case. O(n) means the work grows in step with the input; O(n²) means doubling the input makes the work about four times larger.
How it works
Count the steps the algorithm takes for an input of size n, keep only the fastest-growing term and drop the constants. 3n² + 5n + 2 becomes O(n²).
Common classes, from fastest to slowest: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic and O(2ⁿ) exponential.