I have a question, about Bachman-Landau. How do you know when a function fits into some notation?
For example does fit into .
Or you just look and see, we had some equations in school but I cant' remember them all.
Thank you for your help.
From where I got x² + 25 and x² + x² is a separate question from whether these inequalities are true. You don't have to understand why I chose these specific expressions, but you do have to understand that if you subtract 6x from x² + 25, where x >= 5 and therefore 6x is nonnegative, then you get a smaller value than x² + 25. Therefore, x² - 6x + 25 ≤ x² + 25. Further, you have to understand that x² ≥ 25 for x ≥ 5. Therefore, if you replace 25 with a bigger value x² in x² + 25, you get a bigger result. So, x² + 25 ≤ 2x².
Hmm, ok now I understand the ineqaulities, but why did you choose those terms? At every single expression there is one less term. So the purpose is to rewrite the function into inequalities.
At your first answer you said if deg(f()) ≤ deg(g()) is true, then the polynomial fits into O(x²), so 2 ≤ 2 is true, therefore it fits.
This is how I understand this.
In this example, ; for and for . Adding these inequalities, we get . This holds when and , i.e., when . Therefore, we can take and and we get, as the definition of big-O demands, that for all . We could also say that for . Then for . There is some trade-off here: we got a smaller (1 instead of 5) but a significantly larger (26 instead of 2). If the polynomial were instead of , then, since for and for , we could say that for . Alternatively, since and for , we have for .
Still another way to prove is is to plot the graphs of the two functions and to note that eventually dominates . (If it did not, then we should plot , , etc. until it dominates the left-hand side). Then we can solve to get . Thus, we can take and .
For more information about the big-O notation see the external links in the Wikipedia article or search this forum.