# Lower bound on worst-case time complexity of all sorting algorithms neglecting reading input and accessing elements time

We know that the worst-case time complexity of any comparison sorting algorithm is $$\Omega(n\log n)$$. Is there a lower bound on the worst-case running time of sorting algorithms of any type? Not just comparison-based? I.e, a lower bound on the sorting problem.

• How you define the problem exactly? Note that, the most general version of sorting actually requires comparison based algorithms, because you don't know anything about elements besides of how they compare. If you restrict your problem to words over a finite alphabet, fractions, etc. then the problem changes and you can do more things. The problem with a "general lower bound" for all this widely different problems is that there's none! For example, sorting a particular kind of input with the guarantee that all elements are equal takes 0 operations... Commented Jul 28, 2021 at 17:41
• @BernardoSubercaseaux So if it requires comparison-based algorithms in the general case the answer is $\Omega(nlogn)$. What I meant was the most general case. And about $0$ operations, Well it's best-case, not worst-case for an input of size $n$.
• As I mentioned, there's no well-defined "more general case". The 0 operations case I mentioned is indeed worst-case: the Turing Machine that does nothing takes 0 operations on any input of size $n$ on said problem, as all inputs come already sorted. Commented Aug 9, 2021 at 1:10
Suppose the input size is $$n$$. The lower bound of any algorithm (such as comparison based or non-comparison based) that solve the Sorting problem is $$\Omega(n)$$ because we need read the input at least once.
• The lower bound $\Omega(n)$ is a tight lower bound, because there is some non-comparison based algorithm that work in linear time, notice that, reading input in efficient manner is a critical concept, i suggest you, look at problem 4-2 (Parameter-passing costs ) in your book. Commented Jul 28, 2021 at 15:16