GATE Overflow | Algorithms | Test 1 | Question: 5

Question

If k is a non-negative constant, then the solution to the recurrence
$T(n) = \begin{cases}  1 & \quad n=1 \\ 3T(n/2) + n & \quad n>1 \end{cases} $

for $n$, a power of 2 is 

• A. $T(n) = 3^{\log_2 n} - 2n$
• B. $T(n) = 2 \times 3^{\log_2 n} - 2n$
• C. $T(n) = 3 \times 3^{\log_2 n} - 2n$
• D. $T(n) = 3 \times 3^{\log_2 n} - 3n$

Answer 1

T(2) = 3T(1) + 2 = 5.

Option A = -1

Option B = 2

Option C = 5

Option D = 3