Algorithms / Recurrence Analysis
Least You Need to Know: Recursion Trees and Recurrence Intuition
Recurrences describe recursive runtime by combining the cost of smaller subproblems with the non-recursive work done at each step. Recursion trees help you see branching, depth, and total work level by level.
The least you need to know
- A recurrence like `T(n)=T(n/2)+1` usually suggests logarithmic depth.
- A recurrence like `T(n)=2T(n/2)+n` often leads to `Θ(n log n)` because each level costs about `n` and there are about `log n` levels.
- Recursion trees separate branching from combine cost.
- The branching factor controls how many subproblems appear on each level.
- The stopping condition matters because it determines the tree depth and base cost.
Key notation
T(n)
runtime on input size n
T(n)=2T(n/2)+n
two half-size calls plus linear combine work
level cost
total work across one recursion-tree layer
Tiny worked example
- Merge sort satisfies `T(n)=2T(n/2)+n`.
- Each level of the recursion tree touches all `n` items overall.
- With about `log n` levels, the total becomes `Θ(n log n)`.
Common mistakes
- Students often analyze only one branch of a recurrence and forget the others.
- Students often mistake tree depth for total work.
- Students often ignore the non-recursive combine cost.
How to recognize this kind of problem
- Ask how many subproblems appear per level.
- Ask how deep the tree goes before the base case is reached.
- Then combine level cost with depth.
Next recommended lesson
Continue through this topic with Least You Need to Know: Recurrence Patterns for Interviews.
Least You Need to Know: Recurrence Patterns for InterviewsRelated lessons
Keep going with nearby lessons in the same topic.