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

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(n2)
c) O(n2logn)
d) O(n2) + O(long)

Answer: c
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(n2logn).

Comments