[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.

Asked By : sudo

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63083

3.2K people like this

 Download Related Notes/Documents