0

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?

Aadith Ramia
  • 10,005
  • 19
  • 67
  • 86

1 Answers1

5

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

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • about O(n) + O(nlogn) = O(n)...that was a mistake ..thanks for pointing out. – Aadith Ramia Feb 23 '14 at 11:55
  • now about length of strings for comparison being taken into account, while it looks logical its strange that we never see this conisdered for general string sorting..it is just said that the sort of strings takes O(n log n), n being the no of strings..why would that be? – Aadith Ramia Feb 23 '14 at 11:57
  • 2
    @Aadith this statement is again not true. Length of strings is always considered when sorting them. You can not ignore complexity of comparison when estimating complexity of sorting – Ivaylo Strandjev Feb 23 '14 at 12:02