Complexity of finding the largest $m$ numbers in an array of size $n$

Problem Detail: 

What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ time. Any comments regarding the proof itself, or the style (i.e. my ideas may be clear but the presentation not).

The original question:

Given $n$ numbers, find the largest $m \leq n$ among them in time $o(n \log n)$. You may not assume anything else about $m$.

My answer:

1. Sort the first $m$ elements of the array. This takes $O(1)$ time, as this is totally dependent on $m$, not $n$.
2. Store them in a linked list (maintaining the sorted order). This also takes $O(1)$ time, for the same reason as above.
3. For every other element in the array, test if it is greater than the least element of the linked list. This takes $O(n)$ time as $n$ comparisons must be done.
4. If the number is in fact greater, then delete the first element of the linked list (the lowest one) and insert the new number in the location that would keep the list in sorted order. This takes $O(1)$ time because it is bounded by a constant ($m$) above as the list does not grow.
5. Therefore, the total complexity for the algorithm is $O(n)$.

I am aware that using a red-black tree as opposed to linked list is more efficient in constant terms (as the constant upper bound is $O(m\cdot \log_2(m))$ as opposed to $m$ and the problem of keeping a pointer to the lowest element of the tree (to facilitate the comparisons) is eminently doable, it just didn't occur to me at the time.

What is my proof missing? Is there a more standard way of presenting it (even if it is incorrect)?

Asked By : soandos

Answered By : Massimo Cafaro

Here is an $O(n)$ algorithm solving the problem.

1. Use the worst-case $O(n)$ selection algorithm to determine the $n-m+1$-th order statistics. Let $k$ be this number, which is the smallest of the $m$ largest numbers we are trying to determine.

2. Now partition the array around the pivot $k$ using the QuickSort partition function. This step takes $O(n)$ too.

3. Output the $m$ largest numbers: these are given by $k$ and all of the numbers in the upper subarray generated by partition in step 2.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1485