Let T(n) be the function defined by T(n)=1 and T(n)=2T(n/2)+√n, which of the following is TRUE?
A. T(n)=O(√n)
B. T(n)=O(log2n)
C. T(n)=O(n)
D. T(n)=O(n2)
Answer:C
Let T(n) be the function defined by T(n)=1 and T(n)=2T(n/2)+√n, which of the following is TRUE?
A. T(n)=O(√n) B. T(n)=O(log2n) C. T(n)=O(n) D. T(n)=O(n2)
Explanation: According to Master theorem