How the calculator works
The calculator calls your function with inputs of size 32, 64, 128 and so on, doubling each time, and times every size.
Fast calls are timed in batches, because a browser's clock only ticks every tenth of a millisecond. Each call gets a fresh input, so a function that sorts in place cannot speed up its own next call.
Then it fits every common class to the timings and picks the one that explains them best. When two classes fit almost equally, it says so.
Common time complexities, fastest first
A rough guide: a modern machine does about a hundred million simple steps a second. The last column is the largest input that fits in one second.
| Class | Typical code | n in one second |
|---|---|---|
| O(1) | Read one element, look up a hash map | any size |
| O(log n) | Binary search, a balanced tree lookup | any size |
| O(n) | One loop over the input, two pointers | 10⁸ |
| O(n log n) | Sorting, a heap of n items | 5·10⁶ |
| O(n²) | Two nested loops over the input | 10⁴ |
| O(n³) | Three nested loops, Floyd-Warshall | 450 |
| O(2ⁿ) | Every subset, naive recursion | 26 |
What a measurement cannot tell you
The calculator measures one kind of input. Quicksort is O(n log n) on random data and O(n²) on some sorted inputs, so try the input type your problem actually gets.
O(n) and O(n log n) are hard to tell apart over a short range, because log n grows so slowly. The result says when it is unsure.
The calculator measures time, not memory. In an interview you still have to explain why, and that is the part worth practising.
From measuring to knowing
Every pattern page names its complexity and says why. Start with the one your problem looks like. All patterns on one page
Link to this page
Free to link from a course page, a README or an article. Copy the HTML:
<a href="https://algopath.pro/big-o-calculator">Big O calculator by AlgoPath</a>