Java – complexity of two dependent loops of an external loop with log n complexity

problem

Calculate 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:

Run logn time of the first cycle The second loop runs n-i times, I starts from N and changes to I / 2 in each outer loop iteration Therefore, the internal circulation operation is as follows:

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

wait

N – 1 time

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

Now this sequence is not arithmetic or geometry Therefore, the formula of N / 2 * (a, l) cannot be applied to it How to further handle this solution or error, and what is the correct method

Note: if n / 2 * (a, l) is applied, the complexity is - N / (2 ^ n) = O (2 ^ n)

Solution

You're on the right track As you said, the inner loop will run the log n times Therefore, 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, when calculating complexity, you are always looking for an upper limit, not an exact number