title: Given two max heaps of size n each, what is the minimum possible time complexity to make a one max-heap of size from elements of two max heaps?
body: <p>Given two max heaps of size n each, what is the minimum possible time complexity to make a one max-heap of size from elements of two max heaps?</p>
  
  <p>I've read a couple of answers and everyone says O(n) is the answer for this since we can put all the elements from both of the heaps into an array of size 2n and then run a build heap algorithm which takes O(n) time complexity. </p>
  
  <p>But consider, this approach: </p>
  
  <ol>
  <li>Take the last elements from both the heaps and determine which one is smallest and put it as a root of the new heap [ O(1)]</li>
  <li>put the older heaps as the child of this new root. </li>
  <li>Run a max heapify algorithm on this new heap [ O(logn) ] </li>
  </ol>
  
  <p>Total T = O(1+logn) = O(logn)</p>
  
  <p>I know that max heapify on a node X assumes that the nodes below X are already max heaps (which is satisfied already in the procedure I told above since both of the old heaps are max heaps by themselves. )</p>
  
  <p>Where am I going wrong ?</p>