Big-O calculator
Run a Python function on bigger and bigger inputs and see which growth curve its work follows.
make_input(n) builds the input for size n (return a tuple to pass several arguments); the last function in the box is the one measured. Ctrl+Enter measures.
How it works
It calls your function with make_input(n) for n = 1, 2, 4, 8 and so on. Each size runs twice: once counting the lines of your code that run, once against the clock. Then it fits each common growth curve to the measurements and names the simplest one that fits well.
Doubling n shows the class at a glance: O(n) work doubles, O(n²) work goes up four times, O(log n) work goes up by one step. Switch the chart to Log scale and every power of n becomes a straight line, steeper for a bigger power.
Common time complexities
| Big-O | Name | Typical code | n = 10 | n = 1,000 |
|---|---|---|---|---|
| O(1) | Constant | Read items[i], look up a dict key | 1 | 1 |
| O(log n) | Logarithmic | Binary search, a balanced tree | about 3 | about 10 |
| O(n) | Linear | One loop over the data, x in a list | 10 | 1,000 |
| O(n log n) | Linearithmic | Merge sort, sorted() | about 33 | about 10,000 |
| O(n²) | Quadratic | Two nested loops, bubble sort | 100 | 1,000,000 |
| O(n³) | Cubic | Three nested loops | 1,000 | 1,000,000,000 |
| O(2ⁿ) | Exponential | Recursive Fibonacci, every subset | 1,024 | a 302-digit number |
Time complexity of Python operations
| Type | Operation | Cost |
|---|---|---|
| list | items[i], items[i] = x, len(items) | O(1) |
| list | items.append(x), items.pop() | O(1) on average |
| list | items.insert(0, x), items.pop(0), del items[0] | O(n) |
| list | x in items, items.index(x), items.count(x) | O(n) |
| list | items[a:b], items.copy() | O(b - a), O(n) |
| list | items.sort(), sorted(items) | O(n log n) |
| list | min(items), max(items), sum(items) | O(n) |
| dict | d[key], d[key] = v, key in d, d.get(key) | O(1) on average |
| set | x in s, s.add(x), s.remove(x) | O(1) on average |
| set | a | b, a & b | O(len(a) + len(b)), O(min(len(a), len(b))) |
| str | text[i], len(text) | O(1) |
| str | sub in text, text.replace(...), text.split() | O(n) |
| str | "".join(parts) | O(total length) |
| deque | q.append(x), q.appendleft(x), q.pop(), q.popleft() | O(1) |
| heapq | heappush(h, x), heappop(h) | O(log n) |
| heapq | heapify(items) | O(n) |
n is the length of the list, string or set. "On average" means a rare call is slower (a list that grows has to move to a bigger block now and then; a dict with many clashing keys slows down), but a long run of calls averages out to the cost shown. Try x in items against x in set(items) in the lab and watch the time curve change.
See the algorithms move
The step-by-step animations show where the work goes: binary search halving the list, bubble sort comparing every pair, merge sort splitting and merging, and a min-heap repairing one path at a time.
Frequently asked questions
- Is the answer a proof?
- No. It is a measurement: the curve that best fits what happened on the inputs make_input built. Big-O is usually stated for the worst case, so build the worst-case input (a reversed list for bubble sort, a missing value for a search), and read the code to confirm why it grows that way.
- Why count lines as well as time?
- Line counts are exact: the same code on the same input always runs the same lines, so the curve is clean even for small n. Times wobble with whatever else the computer is doing. But one line can do a lot of work out of sight (sorted(items), x in a long list), which only the time shows. When the two disagree, the page says so.
- What should make_input return?
- The input for size n: a list of n random numbers, a sorted list, a string of length n, or n itself for functions like fib(n). Return a tuple to pass several arguments, as in return items, target. Building the input is not counted or timed.
- Why did it stop at that n?
- It doubles n while the next size fits: at most 300,000 lines in one call, and about ten seconds in all. Exponential code grows so fast that n goes up by one at a time instead. Deep recursion stops at Python's recursion limit, about a thousand calls deep.
- Does it measure memory?
- Not yet: only the work done. Space complexity is usually read from the code: a new list of n items is O(n) extra space, a few variables are O(1).
More: Code visualizer · Coding challenges · Interview questions · Python to flowchart