6
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Look up the phrase "transdichotomous model". $\endgroup$ – Pseudonym Sep 2 '16 at 3:16
  • $\begingroup$ @Pseudonym Thanks, that answers it. I hadn't heard that term. So I assume these educational sources are all using the transdichotomous model. (Edited because I misunderstood at first what this means.) I'm still unsure why they use this model, but that's a different discussion to have... I'll go ask a professor. Thanks again! $\endgroup$ – sudo Sep 2 '16 at 6:58
  • 3
    $\begingroup$ I'm going to suggest that once you've worked out the details, write an answer for your own question. Explaining it will be very educational for you. $\endgroup$ – Pseudonym Sep 2 '16 at 7:53
  • 2
    $\begingroup$ Just as another comment, one of the things that complicates the way we talk about this is that complexity classes like "P" and "NP" are defined in terms of Turing machines; a language is in "P" if its language can be accepted in $O(p(n))$ time on a deterministic Turing machine where $p$ is a polynomial and $n$ is the number of starting symbols on the tape. This is fine for broad classes like "P", because "polynomial" on a TM is almost always "polynomial" on a word RAM machine. But finer distinctions (e.g. "linear")... not so much. $\endgroup$ – Pseudonym Sep 4 '16 at 23:24
  • $\begingroup$ The answer I got: 2^64 is far beyond any input we'd ever receive, and we'll just assume 64-bit integers are always used. This is reasonable in the real world, but I don't see the harm in including the log term, and I do see harm in leaving it out since big-O is supposed to consider arbitrarily large input. Also, I've looked around and have seen things similar to what you say about TMs. Makes some sense, but since there are ways to abuse it, it doesn't sit well with me. $\endgroup$ – sudo Sep 11 '16 at 17:53
5
$\begingroup$

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.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ I don't understand how bullets 1 and 3 are not contradictory. $\endgroup$ – Raphael♦ Sep 2 '16 at 18:40
  • 1
    $\begingroup$ @Raphael: "$O(1)$ space" without any further details in the context of algorithms and data structures almost always means "$O(1)$ words of space in the word-RAM model with $\Theta(\log n)$-bit words". And bits are always bits, without any ambiguity. $\endgroup$ – Jukka Suomela Sep 2 '16 at 18:46
  • $\begingroup$ I see. Maybe you want to add that to your answer. $\endgroup$ – Raphael♦ Sep 2 '16 at 20:16
  • $\begingroup$ And are words the same as string indexes if you're using the model where words are O(1)? In the data structure I described, the index of the string, not a RAM address, is being stored. You can change the index size without changing the machine's word size. $\endgroup$ – sudo Sep 4 '16 at 21:11
1
$\begingroup$

Depends on which model you are interested in.

On RAMs with the uniform or unit cost model, (not too large) numbers take constant space to store, and constant time to work with.

On RAMs with the logarithmic cost model and TMs, they take logarithmic space.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.