Recurrence Relations – GATE CSE AlgorithmsPractice Questions & PYQs

The naive recursive Fibonacci makes two recursive calls: F(n-1) requiring T(n-1) time and F(n-2) requiring T(n-2) time, plus O(1) for the addition. So T(n) = T(n-1) + T(n-2) + O(1). This recurrence solves to T(n) = O(φⁿ) where φ = (1+√5)/2 ≈ 1.618 (golden ratio), giving exponential time O(2ⁿ) as an upper bound. With memoization (DP), it reduces to O(n).

Here a = 2, b = 2, f(n) = n². Compute n^(log_b(a)) = n^(log_2(2)) = n^1 = n. Compare f(n) = n² with n: f(n) = Ω(n^(1 + 1)) = Ω(n^(log_b(a) + ε)) with ε = 1. Check regularity: a × f(n/b) = 2 × (n/2)² = n²/2 ≤ (1/2) × n² = c × f(n) with c = 1/2 < 1 ✓. This is Case 3. Therefore T(n) = Θ(f(n)) = Θ(n²).

Expanding: T(n) = T(n-1) + 1 = T(n-2) + 2 = ... = T(1) + (n-1) = 1 + (n-1) = n. Therefore T(n) = O(n). This recurrence models algorithms that reduce the problem size by 1 at each step with O(1) work per step, such as linear search or computing factorial iteratively.

A: T(n) = 2T(n/2) + n - Master Theorem Case 2: n^(log_2(2)) = n = f(n), so T(n) = Θ(n log n) ✓. B: T(n) = 2T(n/2) + O(1) - Master Theorem Case 1: f(n) = O(1) = O(n^(1-ε)), so T(n) = Θ(n) ✗. C: T(n) = T(n/3) + T(2n/3) + n - as shown above, T(n) = O(n log n) ✓. D: T(n) = 4T(n/2) + n² - Master Theorem Case 2: n^(log_2(4)) = n² = f(n), so T(n) = Θ(n² log n) ✗.

A: T(n) = T(n-1) + O(1) → expanding gives T(n) = n × O(1) = O(n) ✓. B: T(n) = 2T(n/2) + O(n) → Master Theorem Case 2 gives O(n log n) ✓. C: T(n) = T(n/2) + O(n) → Master Theorem Case 3 (f(n)=n dominates n^(log_2(1))=1) gives O(n) - NOT O(log n) ✗. D: T(n) = 2T(n-1) + O(1) → expanding gives T(n) = 2^(n-1) × T(1) + O(2^(n-1)) = O(2ⁿ) ✓.

Here a = 8, b = 2, f(n) = n². Compute n^(log_b(a)) = n^(log_2(8)) = n^3. Compare f(n) = n² with n³: f(n) = O(n^(3 - 1)) = O(n^(log_b(a) - ε)) with ε = 1. This is Case 1 - recursive work dominates. Therefore T(n) = Θ(n^log_b(a)) = Θ(n³). This recurrence is close to the standard matrix multiplication recurrence.

Expanding: T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = 4T(n-2) + 3 = 2²T(n-2) + (2¹ + 2⁰). Continuing: T(n) = 2^(n-1)T(1) + (2^(n-1) - 1) = 2^(n-1) + 2^(n-1) - 1 = 2ⁿ - 1. Therefore T(n) = O(2ⁿ). This models problems like computing all subsets or naive recursive Fibonacci without memoization.

Using Master Theorem: a=2, b=2, f(n)=n ⇒ Case 2 ⇒ T(n)=Θ(n log n).

A: T(n) = 2T(n/2) + n log n - here f(n) = n log n and n^(log_b(a)) = n. Since f(n) = n log n is NOT polynomially larger than n (it is only a log factor larger), it falls in the gap between Case 2 and Case 3 of the standard Master Theorem and cannot be directly solved by it. B: T(n) = T(n-1) + n - the Master Theorem requires the form aT(n/b), not T(n-k) (decreasing by subtraction). C and D are standard Case 2 forms, solvable by Master Theorem.

Here a = 1, b = 2, f(n) = n. Compute n^(log_b(a)) = n^(log_2(1)) = n^0 = 1. Compare f(n) = n with 1: f(n) = Ω(n^(0 + 1)) = Ω(n^(log_b(a) + ε)) with ε = 1. Check regularity condition: a × f(n/b) = 1 × (n/2) = n/2 ≤ c × n for c = 1/2 < 1 ✓. This is Case 3. Therefore T(n) = Θ(f(n)) = Θ(n).

Expanding: T(n) = T(n/2) + 1 = T(n/4) + 2 = ... = T(1) + log₂n = 1 + log₂n. Therefore T(n) = O(log n). This recurrence models binary search - at each step the problem is halved with O(1) comparison work. After log₂n halvings the base case T(1) is reached.

Here a = 2, b = 2, n^(log_b(a)) = n^1 = n. f(n) = n log n = n × log^1(n) = Θ(n^(log_b(a)) × log^1(n)). This matches the generalized Case 2 of the Master Theorem with k = 1: if f(n) = Θ(n^(log_b(a)) × log^k(n)), then T(n) = Θ(n^(log_b(a)) × log^(k+1)(n)). With k = 1: T(n) = Θ(n × log²(n)) = O(n log² n).

Using Master Theorem: Case 2 extended ⇒ T(n) = Θ(n log² n).

a=4, b=2, log₂4=2. f(n)=n is O(n^(2-ε)) for ε=1 → Case 1 → T(n) = Θ(n²).

Expanding by substitution: T(n) = T(n-1) + n = T(n-2) + (n-1) + n = ... = T(1) + 2 + 3 + ... + n = 1 + (n(n+1)/2 - 1) = n(n+1)/2. Therefore T(n) = O(n²). This recurrence models selection sort - at each step we do O(n) work to find the minimum, and repeat for n-1 steps.

Using recursion tree: each level sums to n (n/4 + 3n/4 = n), depth is log₄/₃(n) → Θ(n log n).

The Master Theorem has three cases based on comparison of f(n) with n^(log_b(a)): Case 1 - f(n) is polynomially smaller: if f(n) = O(n^(log_b(a) - ε)) for some ε > 0, then T(n) = Θ(n^log_b(a)). The recursive work dominates. Case 2 - same order: if f(n) = Θ(n^log_b(a)), then T(n) = Θ(n^log_b(a) × log n). Case 3 - f(n) dominates: if f(n) = Ω(n^(log_b(a) + ε)) with regularity condition, then T(n) = Θ(f(n)).

Here a = 2, b = 2, f(n) = n. Compute n^(log_b(a)) = n^(log_2(2)) = n^1 = n. Compare f(n) = n with n^1 = n: f(n) = Θ(n^log_b(a)) = Θ(n). This is Case 2 of the Master Theorem. Therefore T(n) = Θ(n^log_b(a) × log n) = Θ(n log n). This is the recurrence for Merge Sort.

Let m = log n, so n = 2^m. Define S(m) = T(2^m) = T(n). Then T(√n) = T(2^(m/2)) = S(m/2). So S(m) = S(m/2) + 1. By Master Theorem (or substitution): a=1, b=2, f(m)=1. n^(log_b(a)) = m^0 = 1 = f(m) → Case 2: S(m) = Θ(log m) = Θ(log log n). Therefore T(n) = O(log log n).

The recursion tree method: (1) Draw the tree where each node represents a subproblem and its cost. (2) At each level i, compute the total cost across all nodes at that level. (3) Sum the costs across all levels from 0 to the depth of the tree. This gives the total work T(n). The method is especially useful for non-standard recurrences like T(n/3) + T(2n/3) + n where subproblems have unequal sizes. Option B is the substitution method. Option C is the Master Theorem. Option D is the change of variables technique.