# Thread: Big O notation question

1. Member
Join Date
Oct 2009
Posts
14
Rep Power
0

## 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
Java 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
Java 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,,

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.

3. Member
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

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.

5. Member
Join Date
Oct 2009
Posts
14
Rep Power
0
ohhhh!!!! I get it now thank you!

#### Posting Permissions

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