3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user105620 Oct 29 at 17:06
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Oct 29 at 17:57

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.