Core Techniques

Complexity Analysis

Reason about time and space cost, including hidden loops in Python built-ins.

Easy, about 45 minutes to practise.

1Understand

The idea

Count how many times the innermost work runs as the input grows: one loop over n is O(n), a loop inside a loop is O(n²), and halving each step is O(log n). Python hides loops inside in on a list, slicing, sort and string +. Read the constraints first: they tell you the complexity the intended solution needs.

Intuition

Complexity asks how the work grows with input size. One loop over n is O(n); a loop inside a loop is O(n²); halving the search space each step is O(log n). Constants and lower-order terms drop out, you care about the dominant term.

Python hides loops: x in list, slicing, sort, string + in a loop, and list.pop(0) all cost more than they look. Recursion also costs O(depth) stack space even when the explicit variables look O(1).

Read constraints first. They encode the intended budget: n ≤ 10⁵ usually wants O(n log n) or better; n ≤ 20 often allows O(2ⁿ).

What you will be able to do

  • Estimate complexity from loops
  • Know the cost of in, slicing, sort and pop(0)
  • Pick a target complexity from the constraints

When to use it

  • Constraints like n ≤ 10^5 (needs ≤ O(n log n))
  • "Can you do better?"

2See it

Walkthrough

Nested loop vs one pass

nums = [a, b, c], count how often the inner work runs.

1 / 4

iM
a
b
c
012
i → index 0

One loop over n elements → inner body runs n times → O(n).

for x in nums: work(x)

Live template

Line 1 active

1n ≤ 20 → O(2^n) · n ≤ 500 → O(n³) · n ≤ 10^4 → O(n²) · n ≤ 10^6 → O(n log n) or O(n)

Match algorithm to constraints before you write code. Watch amortised costs (append is O(1) amortised; pop(0) is never). Space includes the call stack and any copies from slicing. When two solutions share the same big-O, prefer the clearer one unless constants matter.

Read the walkthrough as text

Estimate before coding. Problem: for each of n queries, check whether a value appears in an array of size n. Constraints: n ≤ 10⁵.

  1. Brute force: for each query scan the array → O(n²) ≈ 10¹⁰ ops, too slow.
  2. Sort once O(n log n), then binary search each query → O(n log n).
  3. Or put the array in a set once O(n), then each query O(1) average → O(n) total.

The constraints rule out (1) immediately. Choosing (2) vs (3) is a space tradeoff: set uses O(n) memory; sorted array + bisect uses O(1) extra if you may mutate.

3Recognise it

Kinds of problems (5)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Counting nested loops

    Example. n ≤ 10⁵ but your solution has a double loop over the array.

    How. Multiply loop bodies: one pass O(n), nested O(n²); that pattern usually fails large constraints.

  • Hidden costs of built-ins

    Example. Checking `x in lst` inside a loop on a list.

    How. Treat each `in` on a list or slice as O(n); overall cost is loops × hidden inner scans.

  • Recursion and call-stack space

    Example. DFS on a chain of depth n without thinking about memory.

    How. Each active call holds a stack frame, depth d uses O(d) space even if work per node is O(1).

  • Amortised cost (list append, dynamic arrays)

    Example. Millions of appends vs millions of insert(0, x).

    How. Append is amortised O(1); shifting from the front is O(n) per op. Pick the structure to match.

  • Choosing a target from input constraints

    Example. n = 2×10⁵, what complexity must the intended solution have?

    How. Map constraint bands: ≤10⁴ often O(n²) ok, ≤10⁶ needs O(n) or O(n log n), ≤20 often exponential is expected.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Hidden loop

    Why it happens. Built-in checks look like O(1) in code even when they scan the whole collection.

    How it fails. `if x in nums` inside a loop on a list of size n costs n² total, TLE on n = 10⁵.

    Fix. Account for every scan: list membership, slice copy, pop(0), and sort inside your loop count.

  • Constraints ignored

    Why it happens. A correct-looking O(n²) solution still fails when the judge allows much larger n.

    How it fails. n = 3×10⁵ with nested loops over all pairs, billions of iterations.

    Fix. Read n first. Pick a target complexity, then choose the pattern that fits (hash map, two pointers, etc.).

  • Stack space ignored

    Why it happens. Recursion depth is easy to forget when only time is discussed.

    How it fails. DFS on a path of 10⁵ nodes hits RecursionError before running out of time.

    Fix. State space cost: recursion adds O(depth); switch to an iterative stack or tail-friendly loop when depth ≈ n.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons