title: Wouldn't this algorithm run in O(m log n)?
body: <p>I am working on an interview question from 
  <a href="http://www.glassdoor.com/Interview/Given-a-list-of-one-million-numbers-how-will-you-find-the-top-n-numbers-from-the-list-in-an-efficient-way-QTN_181196.htm" rel="nofollow"> Glassdoor Software Engineer</a></p>
  
  <p>The question is<BR>   <blockquote>&nbsp; &nbsp; Given a list of one million numbers, how will you find the   top n numbers from the list in an efficient way </blockquote></p>
  
  <p>Here is a solution an author gave from same link </p>
  
  <ol>
    <li>create a min heap</li>
    <li>take first n of m elements and place in the heap <em>(O(n))</em></li>
    <li>for each (m-n) remaining elements, if it is greater than find-min of the heap, insert into heap and delete min. (worst case <em>O((m-n)log n</em>) if the list is sorted.</li>
  </ol>
  
  <p>net result is you can do this in <em>O(n)</em> memory usage and worst-case <em>O((m-n)logn)</em> runtime. 
  <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;I agree with the author's algorithm and the author's assessment of the space complexity of this algorithm. What I have an issue with is the author's analysis of the runtime for insertion into heap and overall time  </p> <p>For the step "take first n of m elements and place in the heap", wouldn't that run in <em>O(nlogn)</em>? At least according to my class notes <a href="https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-04/12-pq-heap.pdf" rel="nofollow"> Heap Add</a>, insertion would be <em>O(logn)</em> and because you are inserting n elements, the runtime of that whole step would be <em>O(nlogn)</em>.</p> <p>Taking that into consideration, wouldn't the overall runtime  of this entire algorithm be, using big oh addition from <a href="http://www.augustana.ualberta.ca/~hackw/csc210/exhibit/chap04/bigOhRules.html" rel="nofollow">Big Oh Addition</a> </p> 
   <pre> <em>O(nlogn + (m-n)logn) = O(mlogn)</em> </pre></p>