Complexity explorer
Drag the input size and watch which growth classes survive. This is the fastest way to build the instinct interviewers test.
Input size
n = 1,00010^3.0
Budget assumed at 10^8 simple operations per second, the usual rule of thumb for a one second limit. Real constants, cache behaviour and language overhead all move this, so treat it as an order of magnitude.
Growth curvesboth axes logarithmic one second budget
Constraint decoder
The constraints in a problem statement usually name the algorithm. Pick a band to see what still fits.
ClassWhere you meet itOperationsAt 10^8/s
O(1)Hash lookup, array index, stack pushFree. Size never matters.1< 1 ms
O(log n)Binary search, heap push, BST descentEffectively free. A billion items is 30 steps.10< 1 ms
O(√n)Trial division primality, sqrt decompositionComfortable well past a million.32< 1 ms
O(n)One pass, two pointers, sliding window, BFSThe target for almost every array question.1,000< 1 ms
O(n log n)Sorting, heap of n, divide and conquerFine to about 10^6. Usually the optimal bound.9,966< 1 ms
O(n²)Nested loops, naive DP over pairs, bubble sortDies around 10^4. Interviewers expect you to beat it.1.0e610 ms
O(n³)Floyd-Warshall, interval DP, matrix multiplyOnly viable to a few hundred.1.0e910.0 s
O(2^n)Subsets, bitmask DP, naive recursionFine to n≈20, hopeless after n≈25.1.1e3013.4e285 years
O(n!)Permutations, brute force TSP, N-Queens without pruningFine to n≈10. Nothing beyond that.∞never finishes
instant< 1 s
noticeable1–60 s
too slowminutes
impossibleforget it
How to use this in a live interview
Read the constraints before the examples. They rule out whole families of solution.
State the complexity of your brute force out loud, then say which band it fails in. That is how you justify optimising.
If n is tiny, say so, and stop apologising for exponential. Backtracking is the intended answer at n ≤ 20.
If n is 10^9, the answer never touches every element. Look for maths, two pointers on a formula, or binary search on the answer.