title: complexity of two dependent for loops with outer loop of log n complexity
body: <p><strong>The problem</strong></p>
  
  <p>Compute the complexity of this algorithm:</p>
  
  <pre><code> for(i=n; i&gt;1;i=i/2)
     for(j=i;j&lt;n;j++){
           statement;
     }
  </code></pre>
  
  <p><strong>What have I done on this topic before:</strong></p>
  
  <p>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:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>and so on till</p>
  
  <p><code>n - 1</code> times</p>
  
  <p>so the general term is <code>n * ((2^n)-1)/(2^n)</code></p>
  
  <p>Now this sequence is not arithmetic nor geometric. So formula of <code>n/2 * (a+l)</code> cannot be applied on it. How do I further proceed with this solution or if it is wrong, then what is the correct method.</p>
  
  <p>Note: If <code>n/2*(a+l)</code> is applied, the resulting complexity is <code>-n/(2^n) = O(2^n).</code></p>