Q63,p3,j14. The solution of the recurrence relation of T(n) = 3T(floor(n/4)+ n is

(A) O(n²)

 (B) O(nlg n)

(C) O(n)

 (D) O(lg n)

Answer C.

Explanation.

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  a=3,b=4,c=1.

3<4

Eq 1 follows hence    O(_nc)=O(n)