Why is the lower bound for sorting strings Ω(d + nlogn)?

Question

I'm taking an Advanced Algorithms course. I'm currently studying efficient algorithms for sorting strings. In this chapter, it is provided a lower bound for the time complexity of $\Omega(d + n\log{n})$, where d is the sum of the distinguishing prefixes of all the strings in our set S and n is the cardinality of the strings set S. The book says this is the minimum number of comparisons any algorithm must take, and I cannot figure out why. Can you help me? Thank you.

Answer 1

I shall modify the question a bit and answer the following version, which I think is more correct:

Prove that the lower bound of any character-comparing string sorting algorithm is $\Omega(d + n \log n)$, where $d$ is the sum of the lengths of the distinguishing prefixes of all the strings in our set $S$ and $n$ is the cardinality of the strings set $S$.

Term $d$ stems from the requirement of reading that many characters. If the first $k$ characters of two strings are the same, then one needs to check the $k+1$st character of those strings. Without reading the first $k$ of both, one cannot be ensured that the first $k$ characters are the same.

Note that, this explanation does not mention any requirement about repeated readings. This is a lower bound: It just mentions that the algorithm needs to access all of the characters of the distinguishing prefixes at least once.

$n$ is the number of elements in our set. To sort the strings, we need to compare and sort at least the distinguished characters of the set. So, sorting $n$ strings cannot be faster than sorting $n$ characters. In a character-comparing sorting algorithm, that cannot be done faster than $\Omega(n \log n)$.

Thus, the overall lower bound is $\Omega(d + n \log n)$.

Answer 2

The time complexity you indicated is the lower bound of your specific problem. A lower bound is the worst-case running time of the most optimized TM that recognizes membership in the language.

Lover bound for sorting algorithms is $\Omega(n \log n)$ this means that it is not possible to do better than this and all the sorting cases (instances) may have a temporal complexity $t \geqslant\Omega(n \log n) $.

For a simple proof of the former lower bound you can take a look at this.