Skip to content
GATETECH
Official PYQ · 2002Q1.3Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2002 Q1.3 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

The solution to the recurrence equation T(2k)=3T(2k−1)+1,T(1)=1T(2^k) = 3T(2^{k-1})+1, T(1) =1 is

Choose one option
View worked solution

Answer: B

We are given the recurrence relation:

T(2k)=3T(2k−1)+1T(2^k) = 3T(2^{k-1}) + 1

with the base case T(1)=1T(1) = 1. Since 1=201 = 2^0, we have T(20)=1T(2^0) = 1.

Let tk=T(2k)t_k = T(2^k). We can rewrite the recurrence in terms of kk as:

tk=3tk−1+1for k≥1t_k = 3t_{k-1} + 1 \quad \text{for } k \ge 1

with the base case t0=1t_0 = 1.

By expanding this recurrence relation step-by-step:

tk=3tk−1+1=3(3tk−2+1)+1=32tk−2+3+1=32(3tk−3+1)+3+1=33tk−3+32+3+1  ⋮=3kt0+∑i=0k−13i\begin{aligned} t_k &= 3t_{k-1} + 1 \\ &= 3(3t_{k-2} + 1) + 1 = 3^2 t_{k-2} + 3 + 1 \\ &= 3^2(3t_{k-3} + 1) + 3 + 1 = 3^3 t_{k-3} + 3^2 + 3 + 1 \\ &\ \ \vdots \\ &= 3^k t_0 + \sum_{i=0}^{k-1} 3^i \end{aligned}

Substituting t0=1t_0 = 1 and using the formula for the sum of a geometric progression:

tk=3k+3k−13−1=3k+3k−12=2⋅3k+3k−12=3⋅3k−12=3k+1−12\begin{aligned} t_k &= 3^k + \frac{3^k - 1}{3 - 1} \\ &= 3^k + \frac{3^k - 1}{2} \\ &= \frac{2 \cdot 3^k + 3^k - 1}{2} \\ &= \frac{3 \cdot 3^k - 1}{2} \\ &= \frac{3^{k+1} - 1}{2} \end{aligned}

Thus, the solution is T(2k)=3k+1−12T(2^k) = \frac{3^{k+1}-1}{2}, which corresponds to option B.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions