title: Time complexity of O(n) inside O(logn) outer loop
body: <p>I am trying to figure out the time complexity of this algorithm. A is an array input. The code does not run, by the way, it is for demonstrative purposes.</p>
  
  <pre><code>def func(A):
      result = 0
      n = len(A)
      while n &gt; 1:
          n = n/2
          result = result + min(A[1,...,n])
      return result
  </code></pre>
  
  <p>This assumes array A is of length n. </p>
  
  <p>I would assume the time complexity of this to be O(n(log n)), as the while loop has complexity O(log n), and the min function has complexity O(n). However, this function is apparently of complexity O(n) not O(n(log n)). I am wondering how this could be?</p>