MY question is about storage complexity of a suffix array. According to textbooks it is O(n) with an exact cost that approximates 4n. However a suffix array of a string of length n is an n-size integer array, along an index that maps each substring to the appropriate position of the array. This index has size $1+2+..+n= O(n^2)$. So why the storage cost it is said to be $O(n)$ at the textbooks?

  • 1
    $\begingroup$ This is explained very well in the Wikipedia article, en.wikipedia.org/wiki/Suffix_array. $\endgroup$ – Yuval Filmus Feb 24 '16 at 22:11
  • $\begingroup$ I still can't see how you search for a substring as long as you do not store the substring itself but only its position $\endgroup$ – curious Feb 24 '16 at 22:14
  • $\begingroup$ That's a different question. There is an algorithm for doing that, described in your textbook. $\endgroup$ – Yuval Filmus Feb 24 '16 at 22:15

You don't store the actual suffixes in the array. You only store indices, $n$ of them. Each index takes $O(1)$ space in the RAM model (which is what the textbook is using to count space), so in total the space consumption is $O(n)$. The number of bits used is $\Theta(n\log n)$.

  • $\begingroup$ The question is for the total cost. So i agree there is a need of O(n) for the storage cost of the SA. But there is a need to store the corresponding suffixes isn't it? Not in that array, but the SA itself without the substrings is useless. $\endgroup$ – curious Feb 24 '16 at 22:17
  • $\begingroup$ No, you never store the suffixes explicitly. That's the point of this data structure – everything is stored implicitly. You use the data structure in conjunction with the original string. $\endgroup$ – Yuval Filmus Feb 24 '16 at 22:19
  • $\begingroup$ I can't really get it.Let's say we have a suffix array, ordered by the suffixes, which contains each suffix position. I want to look for some pattern p.How do i perform binary search based on p, if the algorithm does not keep track of each suffix and its position. Or it only keeps track of the starting point of the suffix as an index to its position on the original string and then it traverses the original one to find the end point of the possible match? That way you need the original string right? $\endgroup$ – curious Feb 24 '16 at 23:18
  • $\begingroup$ Your textbook contains all the answers. Unfortunately I'm not an expert so I cannot help you any further. $\endgroup$ – Yuval Filmus Feb 24 '16 at 23:22

You store only the position of suffixes in the index, not the suffixes themselves. So the storage complexity is O(n) for the index. You then have to keep the original string along with the suffixes array. The original string storage complexity is O(n) also by definition.
The whole storage complexity remains O(n).

  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post - you can always comment on your own posts, and once you have sufficient reputation you will be able to comment on any post. - From Review $\endgroup$ – cody Feb 26 '16 at 20:59
  • $\begingroup$ @cody I edited my answer in order to comply, thanks. $\endgroup$ – Manuel Feb 26 '16 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.