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.
جو کم از کم جاننا ضروری ہے
- 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.
اہم علامتیں
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
مختصر حل شدہ مثال
- 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)`.
عام غلطیاں
- 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.
اس قسم کے سوال کو کیسے پہچانیں
- 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.