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.
جو کم از کم جاننا ضروری ہے
- `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.
اہم علامتیں
depth
number of recursive levels
branching factor
recursive calls per level
combine cost
non-recursive work on a level
مختصر حل شدہ مثال
- `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.
عام غلطیاں
- 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.
اس قسم کے سوال کو کیسے پہچانیں
- 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.