Big O notation

[vendetta]

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...

[JosAH]

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

[vendetta]

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.

[JosAH]

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

[vendetta]

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

[JosAH]

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

[vendetta]

well log for both makes sense. Thank you much