NIELIT 2017 July Scientist B (CS) - Section B: 55

Question

Suppose $T(n)=2T(n/2)+n$, $T(0)=T(1)=1$ which one of the following is false?

• A. $T(n)=O(n^2)$
• B. $T(n)=\Theta(n\log n)$
• C. $T(n)=\Omega(n^2)$
• D. $T(n)=O(n\log n)$

Comments

Option c is correct

Answer 1

It is the recurrence relation of Merge−Sort Merge−Sort.

The time complexity of merge sort is  $Θ(nlogn)$.So, it can not be $Ω(n^{2})$