Mustehssun Iqbal - 1 year ago 77
Java Question

# complexity of two dependent for loops with outer loop of log n complexity

The problem

Compute the complexity of this algorithm:

`````` for(i=n; i>1;i=i/2)
for(j=i;j<n;j++){
statement;
}
``````

What have I done on this topic before:

The first loop runs logn times.
The second loop runs n-i times with i starting from n and changing to i/2 in each outer loop iteration. So the inner loop runs like this:

``````n-n                             0 times

n - n/2                        n/2 times

n - n/4                        3n/4 times

n - n/8                        7n/8 times

n - n/16                     15n/16 times
``````

and so on till

`n - 1`
times

so the general term is
`n * ((2^n)-1)/(2^n)`

Now this sequence is not arithmetic nor geometric. So formula of
`n/2 * (a+l)`
cannot be applied on it. How do I further proceed with this solution or if it is wrong, then what is the correct method.

Note: If
`n/2*(a+l)`
is applied, the resulting complexity is
`-n/(2^n) = O(2^n).`

You are on the right track. As you mentioned, the inner loop would run `log n` times. So, the total number of times it runs is:
``````    (n - n/2) + (n - n/4) + ... (log n) times