Results 1 to 5 of 5
Thread: Big O notation question
 10142009, 08:29 AM #1Member
 Join Date
 Oct 2009
 Posts
 14
 Rep Power
 0
Big O notation question
I was having trouble understanding bigO notation so I searched around websites.. then I came across this:
/////////////Random Post//////////////////
...
or (int j = 1; j < n; j *= 2)
sum += j;
is it also O(n)??

this is what i was talking about in my last post:
since the value of j is increasing by a multiple of 2 each time, in an ordered way, think of it as the formula: 2^p. This is more easily seen as a form of log(n), otherwise known as a loop which runs faster than n, in a logorithmic pattern.
Therefore O(log(n))
**As a note, if the question had been:
for (int j = 1; j < n; j += 2) //notice the + instead of *
sum += j;
then it would be O(n), since the end result is running n/2 times, which is simply 1/2*n a coefficient which is dropped, and results in O(n).
/////////////////////////////////////////////
I think I get the concept of ..say.. 3n^2+3n, then turn that into O(n^2).. and why other values doesn't matter and stuff..
but what I don't get is, how they got the equation in the first place, by looking at code.
like example from above
Java Code:(int j = 1; j < n; j *= 2) sum += j;
I don't understand how he got 2^p from
also with
Java Code:for (int j = 1; j < n; j += 2) //notice the + instead of * sum += j;
how did he get 1/2 from?
I hope you understood my question.. it bugs me not understanding BigO Notation fully,,
Thank you in advance!
 10142009, 04:26 PM #2
n/2 is a fraction. 1/2 * n/1 is n/2
your question isn't an issue of understanding Big O it's with understanding fraction multiplication. You seem to have a decent handle on run time notation.Liberty has never come from the government.
Liberty has always come from the subjects of government.
The history of liberty is the history of resistance.
The history of liberty is a history of the limitation of governmental power, not the increase of it.
 10142009, 07:26 PM #3Member
 Join Date
 Oct 2009
 Posts
 14
 Rep Power
 0
no, I didn't mean fraction multiplcation.
What I don't understand is where they got the 1/2 from
 10142009, 07:46 PM #4
I believe it's because your counter is incrementing by 2 instead of 1. so to get from 1 to n would take half as much time.
Liberty has never come from the government.
Liberty has always come from the subjects of government.
The history of liberty is the history of resistance.
The history of liberty is a history of the limitation of governmental power, not the increase of it.
 10142009, 08:07 PM #5Member
 Join Date
 Oct 2009
 Posts
 14
 Rep Power
 0
Similar Threads

Question mark colon operator question
By orchid in forum Advanced JavaReplies: 9Last Post: 12192010, 08:49 AM 
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, 06: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, 10:06 PM
Bookmarks