Complexity of a naive implementation for selecting top largest $k$ values from an array

Question

I came up with the following algorithm to select top (largest) $k$ values in an array arr containing $n$ comparable values ($k \le n$):

• Initialize an empty array output of size $k$, this array is to store the top largest $k$ values from the array arr of size $n$.
• Iterate through the array arr, and in each iteration we will keep track of the minimum item value minValue (and its index minIdx) in output, also the minimum value minExceptMinValue in output but not counting the minValue (along with its index minExceptMinIdx). We do this by:
  • In the first iteration: add minValue to the output array and set minValue = arr[0], minIdx = 0, minExceptMinValue= null and minExceptMinIdx = null.
  • In the second iteration: Add arr[1] to output and set values for minValue, minIdx, minExceptMinValue, minExceptMinIdx accordingly (by comparing arr[1] and arr[0]).
  • In iteration i:
    • If the length of output less than $k$: Append $arr[i] to output and update minValue, minIdx, minExceptMinValue, minExceptMinIdx (by comparing arr[i], minVal and minExceptMinValue).
    • If the length of output greater than $k$: Compare the current value arr[i] with minValue:
      • If arr[i] >= minValue, then compare arr[i] with minExceptMinValue:
        • If arr[i] >= minExceptMinValue set minIdx to minExceptMinIdx and output[minIdx] = minExceptMinValue also output[minExceptMinIdx]=arr[i].
        • If arr[i] <= minExceptMinValue set output[minIdx] = arr[i].
  • In the last iteration return the output array.

My first estimation for the time complexity of this algorithm is n but it's all wrong because otherwise, I would have won the Nobel prize for it since the fastest algorithm for the selection problem is $\sim n\ln(n)$.

But still, I don't see what's wrong with my estimation that the above algorithm's (time) complexity is $\sim n$, it goes through the array just once, isn't it?

Answer 1

You can easily obtain the $k$ largest items in $O(n)$ as follows: 1) determine the $n-k$th item using worst case $O(n)$ select algorithm 2) use worst case $O(n)$ partition algorithm of quicksort, with pivot the $n-k$-th item. The largest $k$ items are then those following the pivot, in the partition containing the items greater than the pivot.

Real world, practical implementation: use quickselect instead of select ($O(n)$ on average instead of worst case).

Answer 2

Algorithm: Extract the first k numbers k steps) and find the value of the k-largest = smallest in k steps.

For k+1 <= I <= n: Let x be the I-th number, ignore if x <= k largest. N-k steps, X is not ignored with probability k/i, so k (log n/k) values x are not ignored.

If x is not ignored, find among the k largest the smallest, replace with x, and find the value of what is now the smallest. 2k steps, executed k log (n/k) times, total 2k^2 / log(n/k) steps.

Finally find the smallest of the k largest values.

Total n + 2K^2 / log (n/k) steps. Much less than 2n if k <= sqrt n. This assumes random numbers. If that is not the case, examine the numbers xi in some random order.

PS when you update minExceptMinValue (the second largest) you need to check the third largest as well, etc. that gives you a factor 2k / log(n/k) in the average case and 2k < n even when k = n.