Gate CS-2014-2 Question Paper With Solutions

Q. 23 Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

T(n) = 2T(n/2) + Logn

(A) Θ(n)

(B) Θ(nLogn)

(C) Θ(n*n)

(D) Θ(log n)

Answer: (A)

Explanation: