Big O notation

• 01-08-2010, 06:21 PM
vendetta
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

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)

I don't understand b or c...
• 01-08-2010, 06:37 PM
JosAH
Quote:

Originally Posted by 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

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)

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
• 01-08-2010, 06:51 PM
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.

"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.
• 01-08-2010, 06:58 PM
JosAH
Quote:

Originally Posted by 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.

"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
• 01-08-2010, 07:20 PM
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
• 01-08-2010, 07:39 PM
JosAH
Quote:

Originally Posted by 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

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
• 01-08-2010, 07:47 PM
vendetta
well log for both makes sense. Thank you much