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.
Least you need to know
T(n)=T(n/2)+1is logarithmic.T(n)=T(n-1)+1is linear.T(n)=T(n-1)+nis quadratic.T(n)=2T(n/2)+nis 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
Worked example
T(n)=T(n-1)+nexpands ton+(n-1)+...+1.- That sum is quadratic.
- By contrast,
T(n)=T(n-1)+1only 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 it
- 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.