Which gives the solution of T(n)=2T(n/2)+ n, T(1) = 1?

GATE 2014 CS (CS2) – Question 23

Algorithms · Divide-and-Conquer · 1 mark · Multiple choice

Which gives the solution of $T(n)=2T(n/2)+\log n$, T(1) = 1?

$\Theta(n)$
$\Theta(n\log n)$
$\Theta(n^2)$
$\Theta(\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\Theta(n)$

Explanation

The comparison function is n^(log₂2)=n. Since log n grows polynomially slower than n, the Master Theorem’s first case applies. Thus **T(n)=Θ(n),A**. Alternatively, the many constant-cost leaves dominate the summed level costs.