UGC NET CSE | December 2012 | Part 3 | Question: 14

Question

Let $T(n)$ be a function defined by $T(n) =1$ and $T(n)=2T (n/2) + \sqrt{n}$, which of the following is true?

• A. $T(n) = O(\sqrt{n})$
• B. $T(n) = O(\log_2 n)$
• C. $T(n) = O(n)$
• D. $T(n) = O(n^2)$

Answer 1

Apply master theorem  u get O(n) is answer.

Answer 2

According to Master's theorem
T(n) =aT(n/b) + nc
a=2, b=2
nc = √n => nc = n1/2 => c=1/2
1. if logba < c, T(n) = Θ(nc),
2. if logba = c, T(n) = Θ(nc log n),
3. if logba > c, T(n) = Θ(nlogba).
Here logba > c, So T(n)= Θ(nlogba)= Θ(n1)= Θ(n)

Answer 3

Explanation: n(logba) = n which is = n^(1-.5) = O(sqrt n)
then by applying case 1 of master method we get T(n) = Θ(n)