Lesson 01 of 16 · 17:41
Time & space complexity
Complexity is not a stopwatch measurement. It is a way to predict how an algorithm behaves when a small input becomes a very large one. We name the input size, identify the work that repeats, and describe how the amount of work grows. This lets us compare solutions without depending on a particular laptop or programming language.
In an interview, complexity is part of the solution, not an afterthought. The constraints often tell you which growth rates are plausible before you write code: an input of 20 may permit exponential search, 100,000 items usually calls for linear or n log n work, and a billion-sized search space may require logarithmic reasoning.
What you should be able to do after this lesson
- Name every input dimension
- Count repeated work and live memory separately
- Connect the constraints to an acceptable growth rate
The mental model
Count how many times the dominant operation can run, express that count as a function of input size, then keep the fastest-growing term.
Recognize it when: Do this analysis after every solution and whenever constraints force you to choose between a scan, nested work, sorting, or extra memory.
The invariant to say aloud: The complexity claim must name the input variable and include hidden work such as copies, hash operations, recursion depth, and output construction.
Learn the ideas one at a time
Concept 1 of 4
Time complexity
Watch from 0:00 ↗Model the number of meaningful operations as n grows. A single pass is O(n); two independent passes are still O(n); a full nested pair is usually O(n²).
Choose one meaningful unit of work—such as a comparison, pointer visit, or hash lookup—and ask how many times it can happen. Consecutive loops add their work, while genuinely nested loops multiply it. A loop nested in another loop is not automatically quadratic: if two pointers only move forward a total of n times, the combined work is still linear.
Walk through an example
For [4, 7, 1, 9], one scan performs four visits. Two separate scans perform eight visits, which is 2n and therefore O(n). Comparing every pair performs 4 × 4 visits; as n grows that becomes O(n²).
In an interview
State what n means, identify the dominant operation, and explain the bound in words before giving the notation.
Concept 2 of 4
Big O
Watch from 3:32 ↗Big O is an upper-bound growth class. Drop constants and lower-order terms because n² eventually dominates 3n + 20, but never drop a separate input dimension such as m.
Big O groups algorithms by long-run growth. Constants and smaller terms matter in production, but they do not change the growth class: 3n² + 20n + 7 is O(n²). Separate inputs must remain separate, however; scanning two unrelated arrays of lengths n and m is O(n + m), not automatically O(n).
Walk through an example
If a solution sorts n values and then scans them, the work is O(n log n) + O(n). The sorting term grows faster, so the combined class is O(n log n).
In an interview
Say whether you are giving worst-case, average-case, or amortized complexity. Interviewers notice when O(1) hash access is presented as an unconditional guarantee.
Concept 3 of 4
Space complexity
Watch from 8:38 ↗Count auxiliary storage, not merely the input. A hash map may use O(n); a balanced recursive call stack uses O(log n); a skewed recursion can use O(n).
Auxiliary space counts memory introduced by the algorithm. A few counters are O(1), a set holding every value is O(n), and recursion consumes one stack frame for every simultaneously active call. Output space is sometimes reported separately, so say what convention you are using.
Walk through an example
A recursive walk down a balanced tree may visit n nodes but keep only O(log n) frames alive. The same code on a chain-shaped tree keeps O(n) frames alive because the height is n.
In an interview
Do not say an in-place-looking recursive solution is O(1) space; include the call stack and any slices, copies, or hidden buffers.
Concept 4 of 4
Alphabet complexity
Watch from 15:57 ↗When a bounded domain participates, keep it visible: O(n + k), where k might be the alphabet, bucket range, or number of possible keys.
Some algorithms use a second bounded domain such as 26 lowercase letters, k buckets, or a numeric range. Treat that domain as a variable until the problem guarantees it is fixed. O(n + k) explains both the input scan and the work needed to initialize or scan the auxiliary domain.
Walk through an example
Counting lowercase English letters takes O(n + 26), which simplifies to O(n). Counting arbitrary Unicode code points or integer values from 0 through k should remain O(n + k).
In an interview
Name the assumption that makes k constant. This prevents a correct-looking complexity claim from silently depending on a restricted alphabet.
Before you call this lesson done
- Define n, m, or k
- Count total pointer movement, not visual nesting
- Include stack, copies, and output
- Check that the result fits the stated constraints
