Mustehssun Iqbal Mustehssun Iqbal - 20 days ago 5
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).

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.