Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Big O notation (from mathematical perspective)

  1. Oct 4, 2008 #1
    1. The problem statement, all variables and given/known data

    Give a clear and concise mathematical definition for Big-O. ("f(n) is O(g(n)) if....")

    2. Relevant equations

    3. The attempt at a solution

    I'm in a discrete math class and overall I understand the concept of run-time analysis. For example, if a variable is declared it would be O(1) because it is constant no matter on the data set.

    Here is an example:

    Code (Text):
    int x = 10 // constant run time.
    And, here is an example of O(n)

    Code (Text):
    for (int i = 0; i < n; i++)
          print "hello\n"
    What I don't understand is how to prove this from a mathematical perspective. What screws me up is this wording (yes, all those parenthesis); f(n) is O(g(n))

    Is there a way that I can rewrite that statement without the parenthesis, or can someone explain this problem in a different way? I am confident I can solve it but I need to understand it first.

    What I think the problem is saying is this.

    There are two equations:
    - f(n)
    - g(n)

    Given a problem I need to show the the function / equation f(n) (whatever it is) has a run time of whatever the function / equation g(n) is. Is this correct?

    Thanks for any assistance.
    Last edited: Oct 4, 2008
  2. jcsd
  3. Oct 9, 2008 #2
    You're not supposed to prove anything. You're only supposed to define big-O notation mathematically.

    Here's some facts that might help you:


    What's the difference between the first two and the third?

    So big O means that the first function is less than or equal to the second function up to a constant. There does not exist a constant c such that n^2<=c*n for all n. That's why n^2=/=O(n). Try to formalize this into a definition
  4. Oct 10, 2008 #3
    oh, thanks grief. i think i have now solved it using your clear explanation. obviously, f(n) has to be less than or equal to to some constant, Z, multiplied by g(n) given that another constant is less then f(n).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook