Time Complexity Calculator (Big O of Your Code, Measured and Explained)

About the Time Complexity Calculator (Big O of Your Code, Measured and Explained)

Paste a JavaScript or Python function, say what its input is (an array, a string, an integer, a graph, or a generator you write) and get its time complexity two ways that check each other.

The static estimate reads the code itself — JavaScript with acorn, Python with Python’s own ast module — and works out, line by line, how many times each line runs and what each run costs: loops with their bounds (a range of n, a variable halved each time, i * i <= n), library calls with their known costs (sorting n log n, in on a list n, a set or dictionary lookup 1 on average, a slice its length) and recursion as a recurrence, solved with the master theorem, a recursion tree or its characteristic root. You also get the extra space: the collections that grow, the copies, and the call stack.

The measurement then runs your function in an isolated sandbox on 8 to 12 growing input sizes within about 10 seconds, with step counters inserted into a copy of your code, so the result does not depend on how fast your device is. The counts are fitted by least squares to 1, log n, √n, n, n log n, n², n³ and exponential growth and drawn on a log-log chart; when the two answers disagree, the page says why. Without a pass the result is a free preview: the static estimate in full and a measurement at 3 sizes; the full measurement, the recurrence’s worked steps, the memory profile and the report unlock with a Pro pass.

Common uses

• Checking the Big O of an interview or contest solution before submitting it.
• Seeing why a function slows down on large inputs: the line that runs n² times stands out in the table.
• Learning the master theorem and recursion trees on your own recursive code, with each step written out.
• Comparing two versions of a function (a list against a set, a sort against a heap) on the same inputs.

How the measurement works

The calculator copies your code and inserts a counter into every loop body and every function, and adds the known cost of library calls from the real lengths at run time (sorting n·log₂n, a scan or a copy n, a hash lookup 1). Your function then runs on fresh inputs of growing size — 4, 8, 16, then larger steps — in a sandbox that is isolated from this site, each size with a freshly loaded copy of your program so a cache never carries over. Growth that speeds up from one size to the next (exponential) switches to small steps, and a run that passes about 100 million steps (3 million in Python) stops itself.

The counts are fitted to each class as a + b·g(n) by least squares weighted by relative error, so small and large sizes count alike; the class with the smallest error wins, and of two that fit equally well the slower-growing one. R² is computed on the log scale the chart uses, and the log-log slope of the largest sizes is shown too (2 means quadratic).

When the estimate and the measurement disagree

• The measurement is lower: a loop or the recursion stops early on these inputs (a break, a return, a found target), or the generated input is not the worst case — quicksort is n log n on random arrays and n² on sorted ones. Try the sorted or reversed input, or write a generator.
• The estimate is higher: work is shared across iterations or calls — a cache, a visited set, appends that are cheap on average — which the line rules count more than once.
• The measurement is higher: a library call costs more than the rules know, or a bound could not be read and was assumed; the table marks every assumption.
• Too few sizes: with fewer than 5 sizes (the free preview measures 3) neighbouring classes such as n and n log n are hard to tell apart.

Costs the rules use

Python: x in list, list.index, list.insert, list.pop(0), a copy and a slice are O(n) (a slice O(k) for k items); x in set, x in dict and a dictionary lookup are O(1) on average; sort and sorted are O(n log n); heapq.heappush and heappop and the bisect searches are O(log n); deque.popleft is O(1). JavaScript: includes, indexOf, slice, concat, spreading, shift and unshift scan or copy, so O(n); Set and Map lookups are O(1) on average; sort is O(n log n) comparisons. Engines may make some operations cheaper in practice (shift on a short array, for example), so the page counts the cost the language defines and says so.

Sources

• TimeComplexity — the cost of CPython’s list, set, dict and deque operations
• ast — Abstract Syntax Trees — how the Python code is read
• tracemalloc — the memory profile
• sys.setrecursionlimit — Python’s recursion limit
• ECMAScript Array.prototype.shift — why shift moves every other item

Limitations

• The static estimate reads code by rules: it understands common loops, recursion and library calls, and marks every bound it had to assume. Code that computes its loop bounds in other ways, uses classes heavily or calls functions through variables may need the measurement to decide.
• Big O is about growth: a measurement tells the class of the counts on the sizes it tried, not the speed in seconds on another machine, and a function whose cost depends on the values (not the size) of its input may need a generator to show its worst case.
• Python runs with its standard library only (no numpy or pandas) and with Python’s default recursion limit; a deeper recursion stops the measurement at that size, and the sizes before it are kept.
• JavaScript runs as a script without a page: import and export and the DOM are not available, and the work an async function does after an await is not counted.
• Java and C++ are not supported.

Privacy

On this device; its files download once

Your code and generator stay in your browser: they run in an isolated sandbox on your device and are never uploaded. Only the language and the input you chose are remembered in this browser.