# Big-Oh Notation

1. Oct 29, 2012

### theRukus

1. The problem statement, all variables and given/known data
Determine the complexity of the following code:

Code (Text):
for (i = 0; i < 2*n; i += 2)
{
for (j=n; j > i; j--)
{
a++;
}
}

3. The attempt at a solution
Well.. The first for block is O( n ) because i is incremented by 2 each loop up to 2n. The second block is O( logn ) as the number of runs gets smaller as j increases.

So.. the whole algorithm is O( n log n ).

Any help is appreciated, I'm pretty bad with Big-Oh notation

2. Oct 30, 2012

### aralbrec

The thing we are counting is how many times "a++" is executed. The inner loop causes it to execute (n-i) times.

The outer loop iterates through values of i in 0,2,4,..2n-2. But the inner loop does not run at all if i>=n. So actually the inner loop only runs for values of i in 0,2,4,n-1, i is even.

Now count how many times "a++" is executed.

Ʃ (n-i) for values of i from 0 to n-1, i is even.

You don't actually have to perform the summation to know it is O(n2). This is because you'll be adding something up like (n=10): 10+8+6+4+2 = 2*(5+4+3+2+1). What's the formula for adding numbers from 1..n?

Another way you could have guessed it is you've spotted the outerloop is O(n). The inner loop is also O(n) since the number of iterations is a function of (n-i). So the total number of inner loop iterations is O(n*n).

For O(lg N) you need to see exponential decay in each iteration... something like the number of iterations on the inner loop decrease by a half, third, whatever in each outer loop iteration. To prove these things, you need to count.

Last edited: Oct 30, 2012