edited by
9,569 views
33 votes
33 votes

Suppose $T(n) =2T (\frac{n}{2}) + n$, $T(0) = T(1) =1$

Which one of the following is FALSE?

  1. $T(n)=O(n^2)$

  2. $T(n)=\Theta(n \log n)$

  3. $T(n)=\Omega(n^2)$

  4. $T(n)=O(n \log n)$

edited by

5 Answers

Best answer
42 votes
42 votes

Applying Masters theorem,

$T(n) = \Theta (n \log n)$

So, it cannot be  $\Omega(n^2)$.

Hence, answer is (C).

edited by
Answer:

Related questions