3
$\begingroup$

Suppose we want to sort an array that contains $n$ different integers in the range $[1,2n]$. It is known that this requires $\Theta(n\log n)$ comparisons. But comparing integers which might be as large as $n$ might requires time $\Theta(\log n)$ since we have to compare them bitwise. So, apparently the runtime complexity of sorting is $\Theta(n\log^2 n)$. Is this correct? If so, why is it taught that the complexity of sorting is $\Theta(n\log n)$? Is there a better algorithm for sorting which runs in time $\Theta(n\log n)$?

EDIT: I understand that the question depends on the computational model. In fact, I just found an interesting unanswered question that specifically asks about the runtime complexity of sorting on a Turing machine. Originally, I had in mind a realistic computer, only with unlimited memory. In such a computer, we can represent arbitrarily large integers (as sequences of bytes). We are given an array that contains $n$ different integers, each of which is between $1$ and $2n$. We measure the clock-time it takes to sort this array, as a function of $n$. What function will we see?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ What is your model of computation? Is it RAM model? $\endgroup$
    – user35837
    Mar 8, 2017 at 13:38
  • $\begingroup$ See en.wikipedia.org/wiki/… $\endgroup$
    – paparazzo
    Mar 8, 2017 at 14:34
  • 2
    $\begingroup$ Your $n$ is not your problem's input length, and in fact, $\Theta \hspace{-0.05 in}\left(\hspace{-0.03 in}n\hspace{-0.04 in}\cdot \hspace{-0.04 in}(\hspace{.02 in}\log(n))^{\hspace{.02 in}2}\hspace{-0.04 in}\right) \: = \: \Theta \hspace{-0.03 in}\left(\text{input_length}\hspace{-0.03 in}\cdot \hspace{-0.03 in}\log(\text{input_length})\right) \;\;\;$. $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user12859
    Mar 8, 2017 at 15:00

2 Answers 2

Reset to default
6
$\begingroup$

Algorithms are usually analyzed using the random access machine model. In this model, arithmetic operations on machine words take time $O(1)$. A machine word contains $O(\log n)$ bits, where $n$ is some natural parameter, say the length of the input (in machine words!).

Given this definition, comparison-based sorting algorithms run in time $O(n\log n)$ as long as the arguments fit in a constant number of machine words.

Sorting algorithms probably take more than $n\log^2 n$ time on a Turing machine, since Turing machines have no random access. Turing machines are not so interesting, however, for analyzing the running time of algorithms, except for special circumstances such as proving results on the Turing machine model itself.

In your particular case, you can actually sort the array in $O(n)$ using counting sort. The $\Omega(n\log n)$ lower bound only holds for some models such as the comparison model.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think counting sort would be O(2n) $\endgroup$
    – paparazzo
    Mar 8, 2017 at 17:50
  • 2
    $\begingroup$ @Paparazzi ... which is the same as $O(n)$. $\endgroup$
    – Yuval Filmus
    Mar 8, 2017 at 18:11
3
$\begingroup$

The correct statement is that any comparison-based sorting algorithm will require $\Theta(n\log n)$ comparisons in the worst case. How long each comparison will take depends on what you're sorting and what model of computation you're using.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Would the down-voter care to explain? $\endgroup$
    – David Richerby
    Mar 9, 2017 at 12:17

Your Answer

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

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