Big O
An upper bound on growth; O(n^2) means at most proportional to n^2 for large n, read off as what happens when n doubles.
Decision · step 3 of 8Complexity in Numbers: Six classes as n doubles
n = 2. Doubling n added 1 to log n (0 to 1), doubled n, roughly doubled n log n (0 to 2), quadrupled n squared (1 to 4) and squared 2 to the n (2 to 4).
What you will see
Drag n from 10 to 10,000 and watch operation counts for O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n) diverge.
Cost
| Space | O(1) |
|---|
How you work with it here
explore, compare two runs, run it on your own input.
Screen readers: Growth curves are described in words and as a table of operation counts for sample input sizes; each concept has a one-sentence spoken definition.
Reduced motion: Curves and counters update without animation.
Leads to
Topics that need this one first.
Taught by the same lesson
Complexity in Numbers covers these too, in the same run.