Algorithms and Data Structures · Senior · Question 44 of 75
What is the time complexity of building a suffix array naively by sorting all suffixes?
- 1O(n), since suffixes are already ordered
- ✓Correct answer: O(n² log n), because comparing suffixes costs O(n)
- 3O(n log n), the same as sorting numbers
Explanation
There are n suffixes and n log n comparisons, each of which may read O(n) characters. Prefix doubling brings it to O(n log n), and SA-IS to O(n). Suffix arrays answer substring queries with binary search.