How is the cost of suffix array generation O(n^2 log n)?

Question

To build a suffis array on a string of n characters,

1. we first generate the n suffixes O(n)
2. and then sort them O(n log n)

the total time complexity apprears to be O(n) + O(nlogn) = O(nlogn).

But I am reading that it is O(n^2 log n) and could not understand how. Can someone please explain?

Answer 1

First of all the statement O(n) + O(nlogn) = O(n) is wrong. O(n) + O(nlogn) = O(nlog(n)).

Second and the reason why you are confused - comparing two suffixes is not constant. As each suffix is a string of length up to n, the comparison of two suffixes is in the order of O(n). Thus sorting n suffixes is in the order of O(n * log (n) * n) = O(n^2 * log(n)).