# Big O notation question

• 10-14-2009, 08:29 AM
kira137
Big O notation question
I was having trouble understanding big-O 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 co-efficient 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 Big-O Notation fully,,
• 10-14-2009, 04:26 PM
xcallmejudasx
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.
• 10-14-2009, 07:26 PM
kira137
no, I didn't mean fraction multiplcation.
What I don't understand is where they got the 1/2 from
• 10-14-2009, 07:46 PM
xcallmejudasx
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.
• 10-14-2009, 08:07 PM
kira137
ohhhh!!!! I get it now thank you!