Results 1 to 10 of 10
Like Tree3Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Bachman-Landau notation and functions

  1. #1
    Member
    Joined
    Mar 2010
    Posts
    96

    Bachman-Landau notation and functions

    I have a question, about Bachman-Landau. How do you know when a function fits into some notation?
    For example does x^2-6x+25 fit into O(x^2).

    Or you just look and see, we had some equations in school but I cant' remember them all.


    Thank you for your help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Bachman-Landau notation and functions

    Quote Originally Posted by Nforce View Post
    I have a question, about Bachman-Landau. How do you know when a function fits into some notation?
    For example does x^2-6x+25 fit into O(x^2).
    For polynomials, the answer is determined by their degrees. More precisely, f(x) is O(g(x)) iff deg(f(x)) ≤ deg(g(x)). For example, x - 6x + 25 ≤ x + 25 ≤ 2x for x ≥ 5, so x - 6x + 25 is O(x).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2010
    Posts
    96

    Re: Bachman-Landau notation and functions

    Ok, I understand the degree of polynomial. But how did you get this expression:

    Quote Originally Posted by emakarov View Post
    ≤ x + 25 ≤ 2x for x ≥ 5, so x - 6x + 25 is O(x).
    And what means "for x ≥ 5"
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Bachman-Landau notation and functions

    I mean that for every x, if x ≥ 5, then x ≥ 25. Therefore, if x ≥ 5, then x - 6x + 25 ≤ x + 25 ≤ x + x = 2x.
    Thanks from Nforce
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2010
    Posts
    96

    Re: Bachman-Landau notation and functions

    Sorry but I still dont' understand, how did you get that x^2 + 25, and then  x^2 + x^2. From where?

    Thank you for your help.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Bachman-Landau notation and functions

    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.
    Thanks from Nforce
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2010
    Posts
    96

    Re: Bachman-Landau notation and functions

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Bachman-Landau notation and functions

    Quote Originally Posted by Nforce View Post
    Hmm, ok now I understand the ineqaulities, but why did you choose those terms? At every single expression there is one less term.
    You are right. The definition of big-O says that we must show that for some constants C and x_0, it is the case that x^2 - 6x + 25\le Cx^2 for all x>x_0. Therefore, the goal is to prove x^2 - 6x + 25\le Cx^2 for some coefficient C. One approach is to bound from above every term in the left-hand side by cx^2 for some c. Then you add them all together and obtain that the left-hand side is bounded from above by (c+c'+\dots)x^2=Cx^2.

    In this example, x^2\le1\cdot x^2; -6x\le 0\cdot x^2 for x\ge0 and 25\le1\cdot x^2 for x\ge5. Adding these inequalities, we get x^2-6x+25\le(1+0+1)x^2. This holds when x\ge0 and x\ge5, i.e., when x\ge5. Therefore, we can take C = 2 and x_0=5 and we get, as the definition of big-O demands, that x^2 - 6x + 25\le Cx^2 for all x>x_0. We could also say that 25\le25\cdot x^2 for x\ge1. Then x^2-6x+25\le(1+0+25)x^2=26x^2 for x\ge1. There is some trade-off here: we got a smaller x_0 (1 instead of 5) but a significantly larger C (26 instead of 2). If the polynomial were x^2 + 6x + 25 instead of x^2 - 6x + 25, then, since 6x\le 1\cdot x^2 for x\ge 6 and 25\le x^2 for x\ge 5, we could say that x^2 + 6x + 25\le 3x^2 for x\ge 6. Alternatively, since 6x\le 6x^2 and 25\le 25x^2 for x\ge 1, we have x^2 + 6x + 25\le (1+6+25)x^2=32x^2 for x\ge 1.

    Still another way to prove x^2 - 6x + 25 is O(x^2) is to plot the graphs of the two functions and to note that x^2 eventually dominates x^2 - 6x + 25. (If it did not, then we should plot 2x^2, 3x^2, etc. until it dominates the left-hand side). Then we can solve x^2 - 6x + 25\le x^2 to get x\ge 25/6. Thus, we can take C = 1 and x_0=25/6.

    Quote Originally Posted by Nforce View Post
    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 correct, but this is a general theorem, and I am not sure you can provide the proof (though it is basically a generalization of the reasoning above). Whether this is sufficient depends on your course. It is possible that you need a way to show that x^2 - 6x + 25 is O(x^2) that you can fully justify.

    For more information about the big-O notation see the external links in the Wikipedia article or search this forum.
    Thanks from Nforce
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Mar 2010
    Posts
    96

    Re: Bachman-Landau notation and functions

    This is the best answer. Thank you. Another thing, what do you mean by "one function dominates another"? Does it mean that one function increases faster then another?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Bachman-Landau notation and functions

    Quote Originally Posted by Nforce View Post
    Another thing, what do you mean by "one function dominates another"? Does it mean that one function increases faster then another?
    Here by " f(x) eventually dominates g(x)" I mean that f(x)\ge g(x) "eventually," i.e., for all x starting from some point x_0. That is, if g'(x) is O(f'(x)), then there exists a constant C > 0 such that Cf'(x) dominates g'(x) (assuming that f'(x) and g'(x) are nonnegative). But, as far as I know, "dominates" does not have a universally accepted precise meaning in mathematics.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Landau inequality
    Posted in the Calculus Forum
    Replies: 0
    Last Post: March 3rd 2010, 11:39 AM
  2. Limit (~ is Landau's symbol in this Qs)
    Posted in the Calculus Forum
    Replies: 2
    Last Post: August 20th 2009, 06:57 AM
  3. Function Notation and Properties of Functions
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: September 8th 2008, 03:19 PM
  4. Replies: 9
    Last Post: September 24th 2007, 08:46 PM
  5. Theta notation for functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 07:54 AM

Search Tags


/mathhelpforum @mathhelpforum