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.