Return to Answer

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

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

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

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

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

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