# Storage cost of a suffix array

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?

• This is explained very well in the Wikipedia article, en.wikipedia.org/wiki/Suffix_array. – Yuval Filmus Feb 24 '16 at 22:11
• 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 – curious Feb 24 '16 at 22:14
• That's a different question. There is an algorithm for doing that, described in your textbook. – 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)$.