
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
Code:
(int j = 1; j < n; j *= 2)
sum += j;
the post says 'look at this code as 2^p, therefore it is O(log(n)).
I don't understand how he got 2^p from
also with
Code:
for (int j = 1; j < n; j += 2) //notice the + instead of *
sum += j;
it says 'end result is running n/2 times, which is simply 1/2*n'
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!

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.

no, I didn't mean fraction multiplcation.
What I don't understand is where they got the 1/2 from

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.

ohhhh!!!! I get it now thank you!