Q12,Paper 3,J 13. The solution of recurrence relation,

T(n) = 2T(floor (n^1/2)) + log n is

(A) O(n log log log n)

(B) O(n log logn)

(C) O(log logn)

(D) O(logn log logn) 

Answer D.

 Master Method:
Master Method is a direct way to get the solution. The master method works only for following type of recurrences 

T(n) = aT(n/b) + f(n) 

highest degree of f(n) is c.

There are following three cases:
T(n)= O(_nc) where a<b^c                       eq 1.

T(n)= O(_nc log n) where b^c=a. eq 2.

T(n)=O(_nlog_ba) where a> b^c.

In our case T(n) = 2T(floor (n^1/2)) + _n1/2

a=2, b=1, c=1/2 Then

b^c=₁1/2< a. eq 3 follows

hence eq3. O(_n log _ba).