Big-Oh Notation Homework: Determine Complexity of Code

[theRukus]

Homework Statement

Determine the complexity of the following code:

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

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

 

[aralbrec]

Homework Statement

Determine the complexity of the following code:

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

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.

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(n²). 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.