Question

If comparison based sorting algorithm is used construct the suffix array, then what will be time required to construct the suffix array?

(a) O(nlogn)

(b) O(n^2)

(c) O(n^2logn)

(d) O(n^2) + O(logn)

The doubt is from Arrays Types topic in portion Arrays Types of Data Structures & Algorithms I

I have been asked this question during an internship interview.

Answer 1

Correct choice is (c) O(n^2logn)

Easy explanation - On average comparison based sorting algorithms require O(nlogn) comparisons. But comparing a suffix takes O(n). So, overall time to construct the suffix array will be O(nlogn) * O(n) = O(n^2logn).