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 bitslength 8 string => index must be at least 3 bitslength 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.
Space complexity of string indices: O(1) or O(log|S|)?
algorithm analysis;strings;space analysis
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.