1
$\begingroup$

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?

$\endgroup$
10
  • $\begingroup$ "some constant $k<1$". Can you explain what "constant" means here? Be as detailed as possible. $\endgroup$
    – John L.
    May 24, 2023 at 18:52
  • $\begingroup$ Sure, updated accordingly and added an example $\endgroup$ May 24, 2023 at 20:35
  • $\begingroup$ It is great to see an example. I claim $n$ is also a constant. At least in your example, $n=4$ is also a constant. What do you think? $\endgroup$
    – John L.
    May 24, 2023 at 22:26
  • $\begingroup$ Seems fair, as the hypothetical algorithm receives an initial array and some real number k, we can choose any positive integer n to represent the length of A $\endgroup$ May 24, 2023 at 22:34
  • $\begingroup$ Would you become a register user? I am afraid I have reached my limit to help an unregistered user. Of course you do not have to register. Others may answer your question anyway. $\endgroup$
    – John L.
    May 24, 2023 at 22:45

2 Answers 2

-1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Thanks for the detailed answer! I’m currently thinking of the case where k is not a constant with respect to n (0.6, 0.999, etc but not logn for example). Where does my logic fail at the disprove attempt? $\endgroup$ May 25, 2023 at 6:49
  • $\begingroup$ When you "choose a $k=0.9999...$, so $\lfloor n^k\rfloor=n-1$", $k$ becomes dependent on $n$, i.e., $k$ is not a constant (with respect to $n$). $\lfloor n^k\rfloor=n-1$ will fail eventually for any constant $k<1$ when $n\to\infty$, however close $k$ is to $1$. $\endgroup$
    – John L.
    May 25, 2023 at 8:12
  • $\begingroup$ If $k$ is not required to be a constant with respect to $nS, then your disprove attempt is correct. $\endgroup$
    – John L.
    May 25, 2023 at 8:23
  • $\begingroup$ @LearningSomeone $k$ a function of $n$ is absurd. Because $m(n)=\lfloor n^{k(n)}\rfloor$ could be any number in $[0,n)$, allowing the trivial worst-case $n-1$, but also the trivial best-case $2$. For this reason, the question should have stated "for any $k$ function of $n$" to have a unique answer. $\endgroup$
    – user16034
    May 25, 2023 at 10:16
  • $\begingroup$ @YvesDaoust Thanks for more explanation and supporting my answer. I guess the downvote on my answer comes from the fact that I was too "soft" on claiming the answer depends on interpretation, although I did write what is the expected correct answer. I might update my answer to be more assertive. $\endgroup$
    – John L.
    May 25, 2023 at 14:27
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.