Given an array of size $n$, return a sorted array of floor($n^k$) elements for some $k<1$

Question

We are given an array of size $n$ (it is not specified if we have an integer array, a specific range or any other assumptions), which might be unsorted, and a real number as a constant $k<1$. We need to prove or disprove that it is possible to output the $\lfloor n^k \rfloor$ smallest elements of a sorted order, in $O(n)$ worst case time complexity.

example: let $A$ be an array of size 4, and let $k=0.6$. The algorithm should output the smallest $\lfloor 4^{0.6}\rfloor \approx \lfloor2.29\rfloor = 2$ items in A in a sorted order.

I have two ideas here, one to prove the statement and one to disprove it, but not sure how can both be possible:

Disprove: Given that we are able to choose a $k<1$ as we wish, choose a $k=0.9999...$ so $\lfloor n^k \rfloor = n-1$. Assuming by contradiction that this algorithm is possible, we can sort the $n-1$ smallest elements of $A$, and then append the largest element in $O(n)$. This leads to a contradiction resulting from the lower bound for comparison based sorting in $\Omega(n\log n)$.

Prove: use the following algorithm:

1. Find $\lfloor n^k \rfloor$'s rank in the array using median of medians and partition the array using it as a pivot.
2. Preform a Heapsort on a min heap created (in $O(n)$) from the elements smaller than $\lfloor n^k \rfloor$ following the partition.

for the sorting part, calculating the time complexity might generally look like this: As $\lfloor n^k \rfloor \le n^k$ , $\lfloor n^k \rfloor * \log(\lfloor n^k \rfloor) \le k*n^k*\log(n)$. As $k<1$ $\lim_{n\to \infty} \frac{k*n^k*\log(n)}{n} = \dots =0 $, so the sorting is in $o(n)$, and the entire algorithm is in $O(n).$

I think my main issue in both is understanding the asymptotic calculation vs the practical matter of sorting an array (or that my math is entirely wrong, which is an option).

What should be the correct idea/solution?

Answer 1

a constant $k<1$

The answer depends on the understanding of the word "constant".

The meaning of "a constant $k$"

Here is the expected interpretation.

You are asked to answer infinitely many questions. One of them is the following.

We are given an array of size $n$. Is it possible to output the $\lfloor n^{0.6} \rfloor$ smallest elements in $O(n)$ worst case time complexity?

The answer to the question above is, as you have proved, yes.

Another such question is the following.

We are given an array of size $n$. Is it possible to output the $\lfloor n^{0.999} \rfloor$ smallest elements in $O(n)$ worst case time complexity?

The answer to the question above is, as you have proved, yes. As you must have noticed, I am repeating myself, except that $0.6$ has been replaced with $0.999$.

Still another such question is the following.

We are given an array of size $n$. Is it possible to output the $\lfloor n^{\frac1{10}} \rfloor$ smallest elements in $O(n)$ worst case time complexity?

The answer is, as you have proved, yes. As you must have noticed, I am repeating myself, except that $0.6$ has been replaced with $\frac1{10}$.

It turns out that whatever number is used to substitute for $0.6$, as long as it is between $0$ and $1$ exclusive, the answer is yes. This is the expected answer.

Nitpicking on your proof

A vital piece is missing from the following statement.

As $k<1$ $\lim_{n\to \infty} \frac{k*n^k*\log(n)}{n} = \dots =0 $, …

It should have been the following.

As $k<1$ is a constant with respect to $n$, $\lim_{n\to \infty} \frac{k*n^k*\log(n)}{n} = \dots =0 $, …

If $k$ is not a constant with respect to $n$, for example $k=\frac{\log(n-1)}{\log n}$, that limit is no longer $0$.

On the other hand, you will probably not see the phrase "is a constant" in the official solution to this problem nor solutions to similar problems, since people will assume that phrase on that spot given the condition "a constant $k$" in the problem statement. In other words, your proof is pretty good.

Answer 2

The "disproof" is wrong, and the answer is positive.

Because there is no $k$ such that

$$\lfloor n^k\rfloor=n-1$$ for all $n$. You may not assume that $k$ is a function of $n$, this would amount to saying "sort any number of smallest elements".

On the opposite, with $m=\lfloor n^k\rfloor$, getting the $m$ smallest elements with Heapsort will take time $O(n+m\log n)$ and for any constant $k<1$,

$$\lfloor n^k\rfloor\log n\le n^k\log n=o(n).$$

This is because

$$\log n=o(n^\epsilon)$$ for any $\epsilon>0$.