title: Space Complexity of Recursive Build-Heap
body: <p>I am trying to resolve the space complexity of the recursive form of Build-Heap.
  This is what I've done so far, and I would like to know where are my mistakes (if there are):</p>
  <p>first of all: Build-Heap is constructed of for-loop, its' time complexity is Theta(n).</p>
  <p>Build-Heap calls Heapify-Down Theta(n) times-(due to Build-Heap time complexity), so:
  Heapify-Down pushes to the space-stack an array of n\i elements each i-recursive-call, this means it uses space complexity of Theta(logn).</p>
  <p>In conclusion: Theta(n)*Theta(logn) = Theta(nlogn).</p>
  <p>I'm not sure about my explanation for the number of time Heapify-Down being called, also i found on the interenet that Build-Heap space complexity is actually Theta(logn) which means my conclusions are wrong.
  Thanks ahead.</p>