Mustehssun Iqbal - 8 months ago 45

Java Question

**The problem**

Compute the complexity of this algorithm:

`for(i=n; i>1;i=i/2)`

for(j=i;j<n;j++){

statement;

}

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`

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)`

Note: If

`n/2*(a+l)`

`-n/(2^n) = O(2^n).`

Answer

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
= n*(log n) - (n/2 + n/4 + n/8 + ... up to 1)
= n*(log n) - n*(1/2 + 1/4 + ...)
<= n*(log n) - n because (1/2 + 1/4 + ...) is 1 even if we take all terms till infinity (G.P)
= n(log n - 1), which is O(n*log(n))
```

Remember that when calculating complexity, you are always looking for upper bounds, not exact numbers.

Source (Stackoverflow)