Why this Big O Notation statement is considered true?
n^4 + 10000n^4.5 = O(0.0001 ∗ n^5)
If the power of the n is not an integer, do we need to round it up?
Asked
Active
Viewed 90 times
0
Barreto
- 374
- 2
- 14
-
3The left hand side is also in O(193738387*n^16336) - the factor does not matter, the exponent in the O is larger than the largest on the left hand side, that is all that matters for now. – luk2302 Oct 15 '22 at 08:22
-
i don't understand what do u mean. i mean usually if it's 2n it becomes O(n), as we need to drop the coefficient but that's not the case for powers right? n^2 is not equal as O(n^3) ? so why it's true? – ForeverLearner Oct 15 '22 at 08:53
-
1You misunderstand O. 17n is in O(n) but also in O(n^162) and also in O(n^1.0000001 – luk2302 Oct 15 '22 at 12:44
-
It just makes sense to use the closest O to what you have. But any higher power of n inside O is fine as well. – luk2302 Oct 15 '22 at 12:57
-
And yes n^2 is in O(n^3), for any r>=2 n^2 is in O(n^r) – luk2302 Oct 15 '22 at 18:07
-
oh i seee, so because the right side is still going to be larger, the left side is going to be included in the big o of the right side. then i would like to ask one more question, there's another statement marked as false "2^ = O(^100)" isn't it suppose to be true then? – ForeverLearner Oct 16 '22 at 02:18
-
No, that you have exponential va polynomial time complexity and exponential dominates that: https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time – luk2302 Oct 16 '22 at 06:20
-
oh okayy i get it. Thankss!! – ForeverLearner Oct 16 '22 at 07:16