Question

Suffix array can be created in O(nlogn) time.

(a) True

(b) False

The origin of the question is Arrays Types in section Arrays Types of Data Structures & Algorithms I

I had been asked this question in class test.

Answer 1

Right answer is (a) True

Easiest explanation - Suffix array can be constructed in O(n^2logn) time using sorting algorithms but it is possible to build the suffix array in O(nlogn) time using prefix doubling.