Big-O Complexity Chart
Plot O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ) and O(n!) side by side and read the real operation counts at your n: how long each takes, the largest n that fits in one second, and a table of common algorithms with sourced Big-O.
How to Use
- Pick the class you care about in the bar, from O(1) to O(n!). The four readouts show its operation count at n, the time it takes, the largest n that fits in one second and how it compares with O(n log n).
- Set n with the slider (1 to 10¹²) or type it, for example 1000 or 1e6. The chart redraws from n = 1 to your n.
- Switch the y-axis between Log and Linear, and tap the legend chips to hide or show classes. On the linear axis the fast-growing curves leave through the top, which is the point.
- Change Operations per second if you want a different speed. The default, 10⁸ simple operations a second, is a rough assumption: real programs can be 100 times faster or slower.
- Use Which is faster? to compare two algorithms at different sizes, with constant factors: 1·n² at n = 100 against 1·n log n at n = 10,000, or 100·n against n².
- Read Show Work for the arithmetic of every class at your n. The address keeps
?n=,?class=and the rest, so a link reopens the same chart.
Worked Example
Every class at n = 1,000, with logarithms in base 2 and a rough 10⁸ simple operations a second:
O(1): 1 operation, 10 ns.
O(log n): log₂ 1,000 = ln 1,000 / ln 2 = 6.9078 / 0.6931 = 9.966 operations, 99.7 ns.
O(n): 1,000 operations, 10 µs.
O(n log n): 1,000 × 9.966 = 9,966 operations, 99.7 µs.
O(n²): 1,000 × 1,000 = 1,000,000 operations, 10 ms.
O(n³): 1,000³ = 1,000,000,000 operations, 10 s.
O(2ⁿ): 2¹⁰⁰⁰ = 10^(1,000 × 0.30103) = 10^301.03 = 1.07 × 10³⁰¹ operations, 3.4 × 10²⁸⁵ years.
O(n!): 1,000! = 4.02 × 10²⁵⁶⁷ operations, 1.28 × 10²⁵⁵² years.
The jump from n log n to n² is the one people meet most: 1,000,000 / 9,966 = 100.3 times more work at n = 1,000, and the gap widens as n grows (at n = 1,000,000 it is 50,172 times). At 10⁸ operations a second the largest n an O(n²) algorithm handles in one second is √10⁸ = 10,000; for O(n log n) it is 4,523,071, because 4,523,071 × log₂ 4,523,071 = 99,999,994 is just under 10⁸. Open n = 1,000 in the chart.
The common mistake: “the lower Big-O is always faster”. Big-O ignores constant factors. Take an O(n) algorithm that does 100 steps per item, 100·n, against an O(n²) algorithm that does n² steps. At n = 50 the linear one does 100 × 50 = 5,000 steps and the quadratic one 50² = 2,500, so the O(n²) algorithm is 2 times faster. They cross where 100·n = n², at n = 100 (10,000 steps each). From there the O(n) algorithm wins by more and more: at n = 1,000 it does 100,000 steps against 1,000,000, 10 times fewer. O(n) means “eventually smaller, for large enough n”; it does not say where “eventually” starts. Compare them at n = 50.
Show Work
How It Works
How the numbers are made. Every count is worked as a base-10 logarithm, so 2ⁿ and n! at n = 1,000,000 never overflow: log₁₀ 2ⁿ = n × 0.30103, and log₁₀ n! is exact up to n = 170 and uses the log-gamma function above that (it matches 1,000! = 4.02 × 10²⁵⁶⁷). Counts below 10¹⁵ are printed in full. The chart plots every visible class from n = 1 to your n; the log axis reaches the largest polynomial curve at your n (at least 10¹², at most 10¹⁰⁰), so 2ⁿ and n! usually leave through the top, marked with an ↑ label where they cross it. On the linear axis the top is the selected class at n. Hover or tap the chart to read every class at one n.
Common algorithms and their Big-O
| Algorithm or operation | Big-O | Source |
|---|---|---|
| Sorting (compares) | ||
| Selection sort | O(n²) best, average and worst | algs4 cheatsheet |
| Insertion sort | best O(n) · avg O(n²) · worst O(n²) | algs4 cheatsheet |
| Bubble sort | best O(n) · avg O(n²) · worst O(n²) | algs4 cheatsheet |
| Mergesort | O(n log n) best, average and worst | algs4 cheatsheet |
| Quicksort | best O(n log n) · avg O(n log n) · worst O(n²) | algs4 cheatsheet |
| Heapsort | best O(n)* · avg O(n log n) · worst O(n log n) | algs4 cheatsheet (*n log n if all keys are distinct) |
| Python list.sort() | O(n log n) | Python TimeComplexity |
| Searching and symbol tables | ||
| Sequential search (unordered list) | O(n) average and worst | algs4 cheatsheet |
| Binary search (sorted array): search · insert | O(log n) · O(n) | algs4 cheatsheet |
| Binary search tree, unbalanced: search, insert | avg O(log n) · worst O(n) | algs4 cheatsheet, §3.2 |
| Binary search tree, unbalanced: delete | avg O(√n) · worst O(n) | algs4 cheatsheet (Hibbard deletion) |
| Red-black BST or AVL tree: search, insert, delete | O(log n) worst | algs4 cheatsheet, §3.3 |
| Hash table (separate chaining or linear probing) | avg O(1)* · worst O(n) | algs4 cheatsheet (*uniform hashing assumption) |
| Priority queue (binary heap) | ||
| Insert · delete-min · find min | O(log n) · O(log n) · O(1) | algs4 cheatsheet |
| Graphs (V vertices, E edges, worst case) | ||
| Depth-first or breadth-first search | O(E + V) | algs4 cheatsheet |
| Dijkstra (non-negative weights) · Prim MST | O(E log V) | algs4 cheatsheet |
| Kruskal MST | O(E log E) | algs4 cheatsheet |
| Bellman–Ford (no negative cycles) | O(V (V + E)) | algs4 cheatsheet |
| Floyd–Warshall, all pairs | O(V³) | algs4 cheatsheet |
| Python built-ins (CPython) | ||
| list: index a[i], append, pop() | O(1) (append amortized) | Python TimeComplexity |
| list: insert, pop(0), x in list | O(n) | Python TimeComplexity |
| dict: d[k], d[k] = v, k in d | avg O(1) · amortized worst O(n) | Python TimeComplexity |
| set: x in s | avg O(1) · worst O(n) | Python TimeComplexity |
| collections.deque: appendleft, popleft | O(1) | Python TimeComplexity |
| JavaScript | ||
| Map get / has, Set has | sublinear on average (required by the spec) | MDN Map, MDN Set |
Sources: R. Sedgewick and K. Wayne, Algorithms, 4th ed., Algorithms and Data Structures Cheatsheet (sorting, priority queue, symbol table and graph tables, orders of growth, the Big-O definition), §1.4 Analysis of Algorithms, §3.2 Binary Search Trees and §3.3 Balanced Search Trees; the Python wiki’s TimeComplexity page (CPython); MDN’s Map and Set pages. The algs4 sorting table counts compares, which is why it is quoted per case.
Where Big-O Comes From
The O symbol is older than computers. Paul Bachmann used it in number theory: his book Die analytische Zahlentheorie (1894) writes an error term as O(n log n), the same expression this chart calls linearithmic. It meant then what it means now: a quantity that grows no faster than a constant times n log n.
Computer scientists adopted the notation to describe running time, and in April 1976 Donald Knuth published “Big Omicron and big Omega and big Theta” in ACM SIGACT News (volume 8, issue 2, pages 18–24), about the three related symbols. Today O gives an upper bound, Ω a lower bound and Θ both at once; the algs4 cheatsheet lists all three with their formal definitions, alongside tilde notation (~), which keeps the leading constant: insertion sort uses ~ ¼n² compares on average, which is O(n²).
Sedgewick and Wayne’s approach in §1.4 is to treat running time scientifically: observe, form a hypothesis such as “the running time is ~ a·n³”, predict, and check with a doubling experiment that runs the program on inputs of size n, 2n, 4n and so on. Their brute-force 3-sum program is the worked case: its order of growth is n³, and it uses ~ n³/2 array accesses.
About This Tool
This chart plots the eight complexity classes taught in every algorithms course, from O(1) to O(n!), on one set of axes from n = 1 to whatever n you choose, up to a trillion. For the class you select it gives the exact operation count at that n, the time at your chosen speed, the largest n that fits in one second and the ratio to O(n log n), and Show Work prints the arithmetic for all eight.
What it adds to a static Big-O cheat sheet: real numbers instead of curve shapes, a log axis that keeps 2ⁿ and n! readable, a comparison with constant factors so you can see where one algorithm overtakes another, and a table of common operations where every entry names its source. Everything runs in your browser; nothing you type is uploaded.
It is for students learning Big-O, programmers sizing an input before writing the loop, and anyone preparing for a coding interview who wants numbers behind “n log n is better than n²”.
Related tools: Sorting Algorithm Visualizer, Binary Search Tree Visualizer, and Code Inspector.
Frequently Asked Questions
Is O(n²) always slower than O(n log n)?
No. Big-O describes how cost grows as n grows, not which program is faster at a given size. An O(n²) algorithm on 100 items does 100² = 10,000 steps; an O(n log n) algorithm on 10,000 items does 10,000 × log₂ 10,000 = 132,877. At those sizes the quadratic one does 13.3 times less work. Constant factors matter too: algs4 §2.3 switches quicksort to O(n²) insertion sort for tiny subarrays, with a cutoff anywhere from 5 to 15 items.
What base is the log in O(log n)?
Inside O(·) the base does not matter, because log_b n = log₂ n / log₂ b, a constant factor, and O drops constant factors. For actual counts this tool uses base 2, the natural base for halving: log₂ 1,000 = 9.966, so binary search on 1,000 sorted items needs at most about 10 halvings. The same n in base 10 would give 3, which is why the base is always stated next to a number.
How many operations per second does a computer do?
There is no single number, which is why the field is editable. The default of 10⁸ simple operations a second is a rough planning assumption, not a measurement; a tight loop in a compiled language can do far more, and interpreted code or code that misses the cache far fewer. What does not change is the ratio: at any speed, n = 1,000 makes O(n²) about 100 times more work than O(n log n) (1,000,000 against 9,966).
Why does O(2ⁿ) at n = 100 take longer than the age of the universe?
Because 2¹⁰⁰ = 1.27 × 10³⁰ operations. At 10⁸ a second that is 1.27 × 10²² seconds, or 4.02 × 10¹⁴ years. Each extra item doubles the work, so at 10⁸ operations a second the largest n that fits in one second is 26 (2²⁶ = 67,108,864), and a computer 1,000 times faster only raises that to 36. Exponential algorithms such as enumerating all subsets are only practical for small n.
What does O(1) amortized mean, as in Python’s list.append?
It means that a single call can be slow but any long run of calls averages out to constant time each. Python’s TimeComplexity page lists list append as O(1) in the amortized worst case: the list occasionally grows its storage and copies everything, but that happens rarely enough that n appends cost O(n) in total. Inserting at the front, list.insert(0, x), is O(n) every time because every item must move; collections.deque.appendleft is O(1).
How do I use the Big-O Complexity Chart?
Just type your numbers. The answer shows up right away — there is no button to press. Change anything and it updates by itself.
Do I need to install or sign up for anything?
Not at all — it runs in the browser with nothing to install and no account. After it loads once, it even works without an internet connection.
Is my information private?
Yes. Everything happens in your browser. Nothing you type is sent to a server or saved anywhere.
Common Use Cases
Will my algorithm finish?
Set n to your input size and the class of your algorithm. At n = 1,000,000 an O(n²) loop is 10¹² steps, 2.78 hours at 10⁸ a second; O(n log n) is 19,931,569 steps, 199 ms.
Competitive programming limits
Read the largest n in one second: at 10⁸ operations a second that is 10,000 for O(n²), 464 for O(n³), 26 for O(2ⁿ) and 11 for O(n!), so an n ≤ 20 limit hints that exponential search is expected.
Interview answers with numbers
Explain why binary search beats a linear scan: on a sorted list of 1,000,000 items, 19.93 halvings against up to 1,000,000 comparisons.
Teach that constants are dropped
Compare 100·n with n²: at n = 50 the quadratic one is 2 times faster (2,500 against 5,000 steps), at n = 100 they tie at 10,000 and at n = 1,000 the linear one is 10 times faster.
Pick a data structure
The table lists sourced costs: a Python dict lookup is O(1) on average, x in list is O(n), a red-black tree is O(log n) even in the worst case, an unbalanced BST is O(n) in the worst case.
Last updated: