Can $n$ elements be sorted in a worst case time of $\sqrt{n}\log n$? Why or why not? I've seen algorithms being sorted in the worst case of $n\log n$, so why can they be or cannot be sorted in $\sqrt{n}\log n$?

  • $\begingroup$ Depend on the data. See counting sort $\endgroup$ – kelalaka Nov 25 '18 at 18:13
  • $\begingroup$ Without any assumptions on the data, any comparison based sorting algorithm takes $\Omega(n \log n)$. See here $\endgroup$ – Gokul Nov 25 '18 at 18:15
  • 1
    $\begingroup$ Have you consulted a textbook, or any reputable resource about it? What makes you think about $\sqrt(n)$, specifically? $\endgroup$ – Raphael Nov 25 '18 at 19:07

This is impossible. You cannot sort $n$ elements without examining each element at least once, which takes at least $n$ operations.

$n=\sqrt{n}\cdot\sqrt{n}\ge\sqrt{n}\cdot\log{n}$ for all $n>1$, assuming the logarithmic base is at least 2. (Of course, if you assume something completely asinine like $\log_{1.000001}n$, it would be technically possible for some values of $n$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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