Made Easy Test Series:Algo- Asymptotic Complexity

Question

$1)n^{2019}=O\left (n^{2020} \right )$

$2)O(n^{2019})=O\left (n^{2020} \right )$

Which one is correct??

---

If $1)$ is correct, why $2)$ not correct?

Answer 1

n= O(n^2) because n^2 always upper-bounds n, because n^2>=n for every +ve value of n you take

But O(n) is not equal to O(n^2) because that will mean O(n^2) =O(n) that is n upper-bounds n^2, but given any value of n>1, this can never be true as n^2>n for n>1.

Just replace n with n^2019 and n^2 with n^2020 for the above problem.

Comments

https://www.youtube.com/watch?v=A03oI0znAoc

---

@Hirak

if we replace $O$ by $\Theta$ or by $\Omega$ then what will be ur ans??

---

For Θ both are false as n^2019 = Θ(n^2019) but NOT Θ(n^2020)

and Θ(n^2019) can never be equal to Θ(n^2020)

Similarly for Ω also both are false, how can n^2019 is lower bounded by n^2020?? the value of  n^2020 will always be greater than  n^2019 for n>1. So it is upper-bounding but NOT lower-bounding .

Answer 2

Strictly speaking the = sign is an abuse of notation. Actually it should be $n^{2019}$ $\in$ O($n^{2020}$), O($n^{2020}$) the set of functions bounded by $n^{2020}$

Comments

yes, but any clear difference that $O(n)\neq O(n^{2})??$

---

@srestha do you know the answer ? I think both should be true, cause all upper bounds to $O(n)$ can be upper bounded by $O(n^2)$.

 

I'm not sure if it makes sense but for all the functions that we pick for left hand side, we can always pick another asymptotically greater function on the right hand side, hence making the Statement valid. Basically what I'm saying is, $O(n) = O(n^2)$ means set of all functions that are upper bounds to $n$ can be upper bounded by set of functions that are upper bound to $O(n^2)$

$\Theta(n)$ won't work here, and if we flip the functions on left hand side and right hand side, I think $\Omega(n)$ should work too. 

---

Suppose $5n^2$, $5n^2$ $\in$ $O(n^2)$, but $5n^2$ $\notin$ $O(n)$. Therefore $O(n^2) \neq O(n)$.

---

but $O(n)$ also equivalent to $O(n^{2})$

right??

---

> but $O(n)$ also equivalent to $O(n^2)$

right??

 

- I think so, yes. Assuming the "equal" sign means the usual notation in computer science, e.g. $n = O(n^2)$ meaning n is upper bounded by $c \cdot n^2$.

---

@toxicdesire

ans given only $1)$

---

No to be equivalent, they must be of equal size. i.e cardinality of $O(n)$ and $O(n^2)$ must be equal i.e contain the same elements(here the elements are the functions), that means $O(n)$ must contain all the functions which are in $O(n^2)$, I showed that $5n^2$ $\in$ $O(n^2)$

but $5n^2$ $\notin$ $O(n)$. Hence $O(n)$ and $O(n^2)$ are not equivalent.

---

@Arkaprava well, there goes ambiguity then. I'm assuming "=" sign has same meaning for statement 1 and 2. 

---

Yes that is what i stated in my answer actually. Otherwise it doesn't make sense.