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

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.

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)$$.

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.

• Ok, I have a clear understanding of what lower bounds are. I just don't understand why the lower bounds for sorting strings adds a d factor in the complexity. – user105620 Oct 29 '19 at 17:06
• That’s because comparing strings doesn’t happen by magic. If the first 20 characters of two strings are the same, that’s 40 characters you must read or you can’t compare the strings. – gnasher729 Oct 29 '19 at 17:57