MIT assignment Doubt

Question

How the worst case of merge sort is O(n^2) according to the given MIT assignment pdf:-

explain ?

Comments

That's true actually. $O(n^2)$ is not a tight upper bound, but it's an upper bound nevertheless. It's a big-oh notation. If it was theta notation, it would have been wrong.

Answer 1

$\begin{align*} & \;\; \;\; \; F(x) = O(G(x)) \\ &\Rightarrow |F(x)| \leq {\bf c}|G(x)| \;\; \text{ for all } x \geq x_0 \text{ and } x_0,c > 0 \end{align*}$

In this QS :

$\begin{align*} &F(x) = n\log_2 n \\ &G(x) = n^2 \\ &\text{We can easily observe that }\;\; n\log_2 n = O(n^2) \;\; \text{ for c = 1 and }x_0 = 2 \end{align*}$

Comments

It means that they are not taking tightest upper bound, which is O(nlogn).

and hence it can be said that it is worst case of merge sort is O(n^2) also

ryt??

---

hence it can be said that it is worst case of merge sort is O(n^2) also  : NO

---

then what??

and what is the difference between upper bound and worst case time complexity??