# Thread: Big O notation

1. Member
Join Date
Jan 2010
Posts
31
Rep Power
0

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

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. Member
Join Date
Jan 2010
Posts
31
Rep Power
0
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. 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.

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. Member
Join Date
Jan 2010
Posts
31
Rep Power
0
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. 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

7. Member
Join Date
Jan 2010
Posts
31
Rep Power
0
well log for both makes sense. Thank you much

#### Posting Permissions

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