Asymtotic notations

Question

In the context of merge sort, which of the following are true?

$1.\ T(n)\ =\ o(n^2)\\ 2.\ T(n)\ =\ O(n^2)\\3.\ T(n)\ =\ \omega(n)\\4.\ T(n)\ =\ \Omega(n) $

Comments

@nitish @manu

if we talk about outplace merge sort  then only 1and 3 is correct because 2 is tightly upper bound and 4 is tightly lower bound bound

---

@abhishek,

Big-Oh is also correct...moreover it is so trivial that no explanation should be needed.

---

@ joshi_nitish  

for this all are correct initally i did wrong comment  but check my comment now

Answer 1

If I need to answer I go with 1st and 3rd,merge sort is nlogn, in Big-oh it is T(n)<=cn^2,but merge sort never can be O(n^2)

and same with omega T(n)>=c.n,but merge always be greater than (n),it but in little-oh say T(n)<c.n^2 and little  omega T(n)>c.n,

Comments

@Learner_jai

in in-place sorting it is theta(n^2)

---

I think only option 1 should be correct because if you take option 3 which means nlogn>n, cancelling n both sides gives logn>1 which is not true when n=1.