1
$\begingroup$

Assume that you are designing a sorting algorithm that uses an operation $x \leq y$ that have 3 possible results:

• $x < y$

• $x = y$

• $x > y$

Can your algorithm do better than ${\cal \Omega}(n \log n)$?

$\endgroup$
  • $\begingroup$ This question is incompletely posed because it doesn't state whether the complexity bounds are for the best case, the worst case or the average case. Any trivial sorting algorithm--such as insertion sort, or bubble sort--will have best-case complexity lower than ${\cal \Omega}(n \log n)$. $\endgroup$ – David G. Stork Sep 27 '17 at 17:28
0
$\begingroup$

I will for simplicity assume that we are just talking about the worst case scenarios. In practical terms though that isn't really something you should take for granted as being the sole indicator of a good algorithm. There's also the best case or the average case scenario (together these $3$ are the algorithms time complexity), and space complexity (how much memory is taken up by the algorithm) etc.

For comparison sorts (Merge Sort, Quicksort, Shell Sort, Insertion Sort, Heapsort etc.) the best known is as far as I know $\mathcal{O}(n\log{}n)$.

However if you have non-comparison sorts like Counting Sort, LSD Radix Sort, MSD Radix Sort, Bucket Sort etc. they can be a lot quicker.

The worst-case for these algorithms usually don't solely depend on the actual input of the thing that you sort, but also other variables. For example for LSD Radix Sort, the worst case is given by the number of keys (size of input) and then the average length of each key.

For most practical purposes though we use Quicksort because it has an average time complexity of $\mathcal{O}(n\log{}n)$ (even though it's worst case is $\mathcal{O}(n^2)$), and a space complexity of $\mathcal{O}(\log{}n)$.

Also remember that Big O notation removes constants for their time complexity/space complexity, Quicksort has the lowest constant here across almost all algorithms, which is an added bonus for sorts of a smaller nature.

$\endgroup$

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.