Results 1 to 7 of 7

Thread: Big O notation

  1. #1
    vendetta is offline Member
    Join Date
    Jan 2010
    Posts
    31
    Rep Power
    0

    Default Big O notation

    I am learning about Big O notation. I am looking at a problem in a book and it says, "Each of the following formulas for the number of operations is some algorithm. Express each formula in big-O notation."

    a) n^2+5n
    b) The number of digits in 2n
    c) The number of times that n can be divided by 10 before dropping below 1.0
    d)100n+5

    my answers are:

    a) O(n^2)
    b) ??
    c) ??
    d) O(n)

    the answer in the book for b and c are the following:

    b) is logarithmic O(log n)
    c) is quadratic O(n^2)

    I don't understand b or c...

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,772
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by vendetta View Post
    I am learning about Big O notation. I am looking at a problem in a book and it says, "Each of the following formulas for the number of operations is some algorithm. Express each formula in big-O notation."

    a) n^2+5n
    b) The number of digits in 2n
    c) The number of times that n can be divided by 10 before dropping below 1.0
    d)100n+5

    my answers are:

    a) O(n^2)
    b) ??
    c) ??
    d) O(n)

    the answer in the book for b and c are the following:

    b) is logarithmic O(log n)
    c) is quadratic O(n^2)

    I don't understand b or c...
    Log(1) == 0, Log(10) == 1, Log(100) == 2, Log(1000) == 3 etc. The Log() function is an adequate measure for the number of digits in a number; it also is the number of times you can divide a number by 10 before it drops below 1.0; play a bit with a couple of numbers (and use a calculator).

    kind regards,

    Jos

  3. #3
    vendetta is offline Member
    Join Date
    Jan 2010
    Posts
    31
    Rep Power
    0

    Default

    Thanks for your help, I'm with you on these 4 calculations:

    Log(1) == 0, Log(10) == 1, Log(100) == 2, Log(1000) == 3
    but I can't see how these plug into the question.



    The second part of your answer sounds like you're talking about c.

    "it also is the number of times you can divide a number by 10 before it drops below 1.0; play a bit with a couple of numbers"

    I am not sure how to do that.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,772
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by vendetta View Post
    Thanks for your help, I'm with you on these 4 calculations:

    Log(1) == 0, Log(10) == 1, Log(100) == 2, Log(1000) == 3
    but I can't see how these plug into the question.



    The second part of your answer sounds like you're talking about c.

    "it also is the number of times you can divide a number by 10 before it drops below 1.0; play a bit with a couple of numbers"

    I am not sure how to do that.
    It's the same for Java as it is for C; notice anything peculiar for the above numbers? The Log of the number equals the number of digits in the number minus one. Constants don't count in big-Oh calculations so the number of digits in a number n equals O(Log(n)). The same reasoning holds for the number of times you can divide a number n by 10. Play with a couple of numbers and see for yourself.

    kind regards,

    Jos

  5. #5
    vendetta is offline Member
    Join Date
    Jan 2010
    Posts
    31
    Rep Power
    0

    Default

    ok, I read you on b now. Thanks

    so you're thinking c is a logarithmic too?

    1000/10=100
    100/10=10
    10/10=1

    3 operations; log 1000 = 3


    10/10=1
    1 operation; log 10 = 1

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,772
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by vendetta View Post
    ok, I read you on b now. Thanks

    so you're thinking c is a logarithmic too?

    1000/10=100
    100/10=10
    10/10=1

    3 operations; log 1000 = 3


    10/10=1
    1 operation; log 10 = 1
    You got it; remember that the big-Oh function is an approximation, it doesn't have to be exact but no other function approximates it better. Here Log(n) is the answer for b) and c)

    kind regards,

    Jos

  7. #7
    vendetta is offline Member
    Join Date
    Jan 2010
    Posts
    31
    Rep Power
    0

Similar Threads

  1. Big O notation question
    By kira137 in forum New To Java
    Replies: 4
    Last Post: 10-14-2009, 09:07 PM
  2. Reverse Polish notation with stacks confusion
    By jigglywiggly in forum New To Java
    Replies: 3
    Last Post: 10-05-2009, 08:40 PM
  3. Big O Notation
    By dsym@comcast.net in forum New To Java
    Replies: 1
    Last Post: 02-21-2009, 07:02 PM
  4. Postfix-Notation
    By little_polarbear in forum New To Java
    Replies: 9
    Last Post: 09-09-2008, 05:24 PM
  5. Big Oh Notation and Heaps
    By gibsonrocker800 in forum Advanced Java
    Replies: 8
    Last Post: 01-25-2008, 11:06 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •