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