MIT_algorithms

Question

I don't understand How?

Comments

yes, because  upperbound of $nlogn$ is $O\left ( n^{2} \right )$

---

which site u got these question?

---

$\text{It's True, because }nlogn = O(n^2). \text {Infact} \ nlogn \in O(n^p) \text{where p>=2}\\
but \ O(nlogn) \text{is the tightest upper bound for merge sort.}$

---

Mam, But i am not getting How can they ask like that ?

 

I am sensing that question is like

Worst case Time Complexity of Merge sort is O(n²) ?

 

I know O(n logn ) is O(n^k)  where k>1 , 

---

They simply asked worst-case time complexity of merge sort is upper bounded by $c.n^2 \ \text{for some} \  c \geq 0$ or not.

---

@Shaik

not getting ur question

upperbound is not a problem for any algo

Answer 1

let a function g(n) , then O(g(n)) will  include set of all function smaller or same order of the growth as g(n) .

now if the g(n)= n²    then O(n²) includes  O(1) ,O(n) ,O(nlogn)    etc...