Discussion Forum
Que.  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:T(n) = O(n)

Similar Questions:
View All Questions on: Discrete Structures
vishnu :(June 23, 2018 04:26:23) 
It's simple the recurrence of merge sort algorithm hence ans will be nlogn. You have given wrong ans. 