Results 1 to 7 of 7
Thread: Big O notation
 01082010, 07:21 PM #1Member
 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 bigO 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...
 01082010, 07:37 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,233
 Blog Entries
 7
 Rep Power
 24
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
 01082010, 07:51 PM #3Member
 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.
 01082010, 07:58 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,233
 Blog Entries
 7
 Rep Power
 24
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 bigOh 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
 01082010, 08:20 PM #5Member
 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
 01082010, 08:39 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,233
 Blog Entries
 7
 Rep Power
 24
 01082010, 08:47 PM #7Member
 Join Date
 Jan 2010
 Posts
 31
 Rep Power
 0
Similar Threads

Big O notation question
By kira137 in forum New To JavaReplies: 4Last Post: 10142009, 08:07 PM 
Reverse Polish notation with stacks confusion
By jigglywiggly in forum New To JavaReplies: 3Last Post: 10052009, 07:40 PM 
Big O Notation
By dsym@comcast.net in forum New To JavaReplies: 1Last Post: 02212009, 07:02 PM 
PostfixNotation
By little_polarbear in forum New To JavaReplies: 9Last Post: 09092008, 04:24 PM 
Big Oh Notation and Heaps
By gibsonrocker800 in forum Advanced JavaReplies: 8Last Post: 01252008, 11:06 PM
Bookmarks