Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

Learn to read complexity

A five-step routine you can run on any solution, and a cheat sheet for what the answers mean.

  1. 1
    Find the loops

    Ask what each loop's bound depends on. A loop from i to n inside a loop over n is n². A loop whose pointer never resets is usually amortized.

  2. 2
    Price the calls

    A call inside a loop costs its own complexity. contains on a list, string concatenation and slicing are all linear.

  3. 3
    Solve the recursion

    Write T(n) in terms of smaller calls. Two calls on n − 1 is 2ⁿ. Two calls on n/2 plus a linear merge is n log n.

  4. 4
    Count memory

    Separate auxiliary space from the input, and do not forget the recursion stack.

  5. 5
    Look for what the inner loop repeats

    If it searches or sums something the outer loop could remember, a HashMap or prefix sum can remove it.

Common complexities
ClassTypical exampleOps at n = 1,000Feels like
O(1)Array index, hash lookup1Constant
O(log n)Binary search10Halving each step
O(n)Single loop1,000Touch each item once
O(n log n)Merge sort, sort then scan10,000Divide, then linear merge
O(n²)Nested loops over the input1,000,000Every pair
O(2ⁿ)Naive Fibonacci, subsets≈ 10³⁰⁰Doubling per element

Turn on Learning mode in the analyzer to get hints before the answer, or browse the pattern library.