Algorithms / Recurrence Patterns
Least You Need to Know: Recurrence Patterns for Interviews
Interview-style recurrence questions usually reduce to a few recognizable patterns. Ask whether the size shrinks by division or subtraction, how many branches appear, and what each level costs.
The least you need to know
- `T(n)=T(n/2)+1` is logarithmic.
- `T(n)=T(n-1)+1` is linear.
- `T(n)=T(n-1)+n` is quadratic.
- `T(n)=2T(n/2)+n` is the classic `Θ(n log n)` pattern.
- The same recursive shape can have very different total work depending on branching and combine cost.
Key notation
depth
number of recursive levels
branching factor
recursive calls per level
combine cost
non-recursive work on a level
Tiny worked example
- `T(n)=T(n-1)+n` expands to `n+(n-1)+...+1`.
- That sum is quadratic.
- By contrast, `T(n)=T(n-1)+1` only accumulates constants, so it is linear.
Common mistakes
- Students often remember only one famous recurrence and force every problem into it.
- Students often count depth but forget branching.
- Students often ignore the size of the non-recursive work on each level.
How to recognize this kind of problem
- Check whether the size shrinks by halving or subtracting one.
- Count how many recursive calls are made per level.
- Then combine depth and per-level work.
Next recommended lesson
Continue through this topic with Least You Need to Know: Recursion Trees, Feasibility Checks, and Pruning.
Least You Need to Know: Recursion Trees, Feasibility Checks, and PruningRelated lessons
Keep going with nearby lessons in the same topic.