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
One loop over n elements → inner body runs n times → O(n).
Live template
Line 1 active
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⁵.
- Brute force: for each query scan the array → O(n²) ≈ 10¹⁰ ops, too slow.
- Sort once O(n log n), then binary search each query → O(n log n).
- 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.