title: What is the running time of this program? (if we have a for loop which is inside a while loop)
body: <pre><code>def hsum(X):
      while len(X) &gt; 1:
          Y=[None]*(len(X)//2)
          for i in range(0,len(X)//2):
              Y[i] =  X[2*i] + X[(2*i)+1]
          X=Y
      return X[0]
  </code></pre>
  
  <p>Here X is an array of integers and the length of X is n=2^k. And the length decreases (as in n//2) after it enters the while loop and that decreased length is the range of the for loop ( for example, n=2^6 = 64 and as it enters the while loop it decreases to n//2, so the range of the for loop is 
  (0, 64/2 = 32). So, the running time of while loop is O(log n), but what would be the running time of the for loop? And what is the running time of the whole code in terms of Big-Oh? </p>