What is the lowest bound for the algorithm?

Question

Let an algorithm which get unsorted array with the size of n. Let a number k<=n. The algorithm prints the k-smallest numbers from 1 to k (ascending). What is the lower bound for the algorithm (for every k)?

1. Omega(n)
2. Omega(k*logn)
3. Omega(n*logk)
4. Omega(n*logn)
5. #1,#2 Are both correct.

Now, from my understanding, if we want to find a lower-bound to an algorithm we need to look at the worst-case. If that the case, then obviously the worst-case is when k=n. We know that sorting an array is bounded by Omega(nlogn) so the right answer is #4.

Unfortunately, I am wrong and the right answer is #5.

Why?

Answer 1

Lets try with Linear time:

1. In order to find the k'th smallest element, we have to use "Randomized-Select" which has the average running time of O(n). And use that element as pivot for the quick sort.
2. Use Quick sort method to split the array[i] <= k and array[i]>k. This would take O(n) time
3. Take the unsorted left array[i]<=k (which has k elements) and do counting sort, which will obviously take O(k+K)
4. Finally the print operation will take O(k)

Total time = O(n)+O(k+K)+O(k) = O(n+k+K)

Here, k is the number of elements which are smaller or equal to K

Answer 2

It can be done in O(n + klogk).

• Run selection algorithm to find the k smallest element - O(n)
• Iterate and return the elements lower/equals k - O(n)
• Another iteration might be needed in case of the array allows duplicates, but it is still done in O(n)
• Lastly, you need to sort these elements in O(klogk)

It is easy to see this solution is optimal - cannot get better than O(klogk) factor because otherwise for assigning k=n you could sort any array better, and a linear scan at least is a must to find the required elements to be printed.