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.
Least you need to know
- A recurrence like
T(n)=T(n/2)+1usually suggests logarithmic depth. - A recurrence like
T(n)=2T(n/2)+noften leads toΘ(n log n)because each level costs aboutnand there are aboutlog nlevels. - 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
Worked example
- Merge sort satisfies
T(n)=2T(n/2)+n. - Each level of the recursion tree touches all
nitems overall. - With about
log nlevels, 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 it
- 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.