Recurrence Relations – GATE CSE AlgorithmsPractice Questions & PYQs

Using the recursion tree: at level 0 cost = √n. At level 1, two subproblems of size n/4, each costing √(n/4) = √n/2. Total level 1 cost = 2 × √n/2 = √n. At level k, 2^k subproblems of size n/4^k, each costing √(n/4^k) = √n/2^k. Total level k cost = 2^k × √n/2^k = √n. Number of levels = log_4(n). Total cost = √n × log_4(n) = O(√n log n). Verifying via Master Theorem: a=2, b=4, f(n)=√n. n^(log_4(2)) = n^(1/2) = √n = f(n) → Case 2: T(n) = Θ(√n log n) ✓.

Here a = 7, b = 2, f(n) = n². Compute n^(log_b(a)) = n^(log_2(7)) ≈ n^2.807. Compare f(n) = n² with n^2.807: f(n) = O(n^(2.807 - ε)) with ε ≈ 0.807. This is Case 1 - recursive work dominates. Therefore T(n) = Θ(n^log_2(7)) ≈ Θ(n^2.807). This is faster than the naive O(n³) matrix multiplication, which was Strassen's key contribution.

Master theorem: a=3, b=3 ⇒ n^log_b(a)=n ⇒ Case 2 ⇒ Θ(n log n).

In the recursion tree for T(n) = T(n/3) + T(2n/3) + cn: at the root, work = cn. At level 1, two subproblems of sizes n/3 and 2n/3 with costs cn/3 and 2cn/3 respectively. Total level 1 cost = cn/3 + 2cn/3 = cn. At level k, all subproblems together have sizes summing to n (the original problem). Total cost at every level = cn = O(n). The number of levels is at most log_{3/2}(n) = O(log n). Total T(n) = O(n) × O(log n) = O(n log n).