Q14,Paper 3,D 12..Let T(n) be the function defined by T(n) = 1 and T(n) = 2T (n/2) + n^1/2, which of the following is TRUE ?

(A) T(n) = O(n)

(B) T(n) = O(log₂n)

(C) T(n) = O(n)

(D) T(n) = O(n²)

Answer(A)

Explanation .

Let T(1)=1

T(2)= 2T(1)+2^1/2= 2+1.141.

T(4)=2T(2)+2.= 2(3.1)+2= 8.2

T(8)=2(8.2)+8^1/2=18.

Hence it is multiple of n so  O(n).