GATE CSE 2005 | Question: 37

Question

Suppose $T(n) =2T (\frac{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

It is the recurrence relation of $Merge-Sort$. The time complexity of merge sort is $Θ(nlogn)$.
The option (C) is false!

---

In option c if it would have been given omega (n) then will it be right?

---

yes @Shubhdwivedi

Answer 1

Applying Masters theorem,

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

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

Hence, answer is (C).

Comments

got now thanks sir

---

arujun sir it means theta determine big oh and omega.

   Or

theta equal to big oh and omega. ???

---

@satbir

Is the comment made by @cse23 correct?

Answer 2

watch first 20 min, you will understand all about notations

https://www.youtube.com/watch?v=P7frcB_-g4w

Answer 3

If you are not getting how Master theorem works step by step, you can refer this blog post:

https://devsathish.wordpress.com/2012/01/19/master-theorem-with-examples/

P.S. Not mine.

Answer 4

Apply masters theorem to the above example,
a=2, b=2, k=1, p=0.
The recurrence relation result will be O(nlogn).