What is the time complexity of building a Suffix Array naively?

What is the time complexity of building a Suffix Array naively?

Approach: Analyze sorting n suffixes of length up to n.

O(n^2 log n). Sorting n strings takes O(n log n) comparisons, and each string comparison takes O(n) time.

Follow-up: What is the complexity of a more efficient approach?

Key concepts: O(n^2 log n), sorting strings.