complexity of two dependent for loops with outer l

问题:

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

回答1:

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.

回答2:

First the calculations

A := (n - n)  + (n - n/2) + (n - n/4)  + ... + (n - n / 2^logn) = 
     log n * (n) - n * (1 + 1/2 + 1/4 + 1/8 + .... 1 / 2 ^ logn)
A > log n * (n)  - n * (1 + 1/2 + 1/4 + 1/8 + .... + 1 / 2^infity) =
     logn * n - n = n(logn - 2)
A < log n * (n)

As you see I have assigned the expression you want to evaluate to A. From the last two inequations it follows the complexity of your algorithm is thetha(n logn)

Here I used the well known geometric progression of (1 + 1/2 + 1/4 + .....) = 2

回答3:

The exact no of times the statement runs is nlogn - 2n(1-1/2^logn)