1
I have a question in Algorithm Complexity. As you can see in the image below, the expressions are equivalent, that is, they have the same qualities and the same dominant term (n²), so because the results are different?
2 answers
1
In fact, it is not completely wrong. Everything I will write here was taken from the book and video lessons of Cormen et al (2002).
To begin with, the Big-O (or O-big) notation serves only for an "upper asymptotic limit". It is important to know this, because the Theta notation (Θ) refers to asymptotic limits a function above and below (i.e., an asymptotic limit "firm", or "fair" in some translations).
When you write normally that f(n) = O(g(n)), is simply stating that some constant multiple of g(n) is an asymptotic upper bound on f(n). The detail is that in big-O notation there is no mention of how much the upper bound is restricted.
That is, the notation says that there is a function f(n) that is O(n<sup>2</sup>) for any value of n, no matter the size chosen, the execution time on that entry has an upper limit determined by the value of f(n).
In theory, therefore, a function f=n2-1 also has an "upper limit" unrestricted O(n3). After all, for all n positive, as n3 is monotically increasing when n > 0, there will be positive constants c and n0, such that 0<= f(n) <= cg(n), for all n >= n0.
Take the test!
However, big-O notation is not used that way. Although there is (and it actually represents) a "set of functions" that make the notation true (basically, in this case, every function that has an upper bound above the function f by a factor c, polynomially), it always uses the most "near) asymptotic limit".
Maybe I was confused, but from 2:51 on: https://www.youtube.com/watch?v=whjt_N9uYFI, Erik Demaine explains very well the mathematical "abuses" of big-O notation (and the fact that the equal sign is asymmetrical is one of them!) demonstrating how these limits work
In fact, he uses the following example: 2n2= O(n3) and explains that this actually means that 2n2 O(n3), that it is part of the "set" of functions bounded asymptotically by O(n3). Understands?
That is, vc can YES, affirm that g(n) = 3n3 + 2n2 + n is O(n4), but this statement is much more "weak" or inaccurate (or rather "asymptotically inaccurate") than saying that g(n) is O(n3), do you understand? Since to prove, by the definition that g(n) above is O(n3) just prove that she is <= 6n3, for n>=0.
I hope to have help to understand this subject, at least a little.
Any questions, go to the comments!
0
There’s absolutely nothing wrong.
If f ∈ O(g) and g ∈ O(h), then f ∈ O(h).
That is, every function f(n) belongs to O(g(n)) if for all n it is true that g(n) >= f(n).
It is clear that for all n it is true that n^3 >= n^2, then f(n^2) ∈ O(n^3).
Browser other questions tagged
You are not signed in. Login or sign up in order to post.
Complexity has nothing to do with result, has to do with... complexity.
– Maniero
Forgive my ignorance, but that symbol on top of the
1has some meaning?– lazyFox
Response to lazyFox 2 - Negative, the line above -1, was a 'p' of the phrase that preceded it.
– Félix
(n 2) is quadratic and O(n k) is polynomial in the size of the input. But this looks like a typo. = p
– viana
What happens in complexity, is that if the function has many terms after it joins them, like (x 3+3x 2+2x+5), you take only the largest term of the function (in this case x 3) to represent the real complexity, so by tending the function to infinity, the rest just becomes irrelevant, see: https://www.desmos.com/calculator/3prowxx1qg
– MarceloBoni
In this case, it also seems to me a typo
– MarceloBoni
Complicated, I already have difficulties in this matter, and the college does not care about students... I thank you for the comments and I will take the answer to my questions as a typo. Thank you all.
– Félix
Is it possible to pass the statement from where you got it? https://i.stack.Imgur.com/Vvjon.png. Or the previous explanation, as it is, this vague medium
– MarceloBoni
Reply to Marceloboni - http://prntscr.com/el62k5 I put the pdf page in lightshot
– Félix
when sending someone a comment, just write @+person’s name :) In fact, right there was f = n 3 - 1 => f = O(n 3)
– MarceloBoni
@Marceloboni - understood, in fact it is a typo XD, thanks for the attention :D, helped me a lot.
– Félix
This might help you: http://bigocheatsheet.com/
– MarceloBoni
@Marceloboni - I will be reading the content, once again, thank you.
– Félix