Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Space complexity of string indices: O(1) or O(log|S|)?

, ,
Problem Detail:

Say you have a string `S` and wish to store indices of it, e.g. letter at index 3 of "toast" is 'a'. Seems that people generally consider an index as taking `O(1)` space to store*. But doesn't it take `O(log(|S|))` space?

If we use binary bits...

• length 4 string => index must be at least 2 bits
• length 8 string => index must be at least 3 bits
• length n string => index must be at least `log(n)` bits

*An example of where I'm seeing `O(1)` suggested: educational sources state that a suffix tree has `O(|S|)` space complexity, where `S` is the input string, because there are `O(|S|)` nodes in the tree, and each node is just an index in the input string. This implies that each index takes `O(1)` space, but this seems untrue to me. Seems like the tree takes `O(|S| log(|S|))` space.

*More examples: Many basic data structures (hash tables, BSTs, etc) use memory pointers (equivalent to string indices), and everyone considers these pointers fixed-size.

#### Answered By : Jukka Suomela

These are correct (unless you explicitly specify a non-standard model of computing):

• \$O(1)\$ space,
• \$O(1)\$ words of space,
• \$O(\log|S|)\$ bits of space.