title: What's the time complexity for max heap?
body: <p>I'm trying to figure out the time complexity for this whole algorithm. Isit O(nlogn) or O(n)? I've been searching online and some says max heap it's O(nlogn) and some are O(n). I am trying to get the time complexity O(n).</p>
  
  <pre><code>def max_heapify(A, i):
      left = 2 * i + 1
      right = 2 * i + 2
      largest = i
      if left &lt; len(A) and A[left] &gt; A[largest]:
          largest = left
      if right &lt; len(A) and A[right] &gt; A[largest]:
          largest = right
      if largest != i:
          A[i], A[largest] = A[largest], A[i]
          max_heapify(A, largest)
  
  
  def build_max_heap(A):
      for i in range(len(A) // 2, -1, -1):
          max_heapify(A, i)
      return A
  </code></pre>