Why is the lower bound for sorting strings Ω(d + nlogn)?
-
06-11-2019 - |
Pergunta
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.
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange