in Algorithms retagged by
1,222 views
0 votes
0 votes

$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?

in Algorithms retagged by
by
1.2k views

2 Answers

1 vote
1 vote
Best answer

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.

edited by
by

4 Comments

0
0

@Hirak

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

0
0

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 .

1
1
1 vote
1 vote
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}$

4 Comments

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.
1
1

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

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