Loading page
About this tool
Look up best, average and worst-case time and space complexity for common algorithms and data structures.
This reference tool looks up the best, average and worst-case time complexity — plus auxiliary space — for the sorting algorithms, search algorithms, data structures and graph algorithms that appear in coding interviews, following the canonical analyses in CLRS (Introduction to Algorithms). Search by name, filter by category, and compare growth classes with a table of approximate operation counts from n = 10 to n = 1,000,000.
Open Time Complexity Cheat Tool on AltFTool — it loads instantly in your browser.
Add your input to the workspace.
Adjust the options until the result looks right.
Copy or download the output and put it to work.
Best, average and worst-case time are listed separately, so the quicksort O(n log n) vs O(n²) distinction is never blurred.
Every entry carries its auxiliary space cost — the figure interviewers ask about right after time.
A side table turns O(n²) vs O(n log n) into actual operation counts at n = 1,000 and n = 1,000,000.
O(n log n) in the best and average case and O(n²) in the worst case, with O(log n) auxiliary stack space. The quadratic case occurs when pivots split the array maximally unevenly — for example naive first-element pivots on already-sorted input — and randomised pivot selection makes it vanishingly unlikely.
Merge sort and heapsort both guarantee O(n log n) in the worst case, which is optimal for comparison-based sorting. Merge sort is stable but needs O(n) extra space; heapsort is in-place with O(1) extra space but unstable. Non-comparison sorts like counting sort reach O(n + k) when the key range k is small.
No — O(1) is the expected cost per lookup, insert or delete with a good hash function and sensible load factor; the worst case is O(n) when every key collides into one bucket. That is why languages like Java switch long collision chains to red-black trees, capping the worst case at O(log n).
At n = 1,000,000 an O(n log n) algorithm does roughly 2×10⁷ operations while an O(n²) one does 10¹² — about 50,000 times more work. At tiny sizes the gap reverses because Big-O hides constants, which is why production sorts use insertion sort below a small threshold.