5 ms·

> If we’re dealing with collections people tend to mean time complexity, because most collections have a space complexity of O(n). I say most, since a common on

• shin_lao 12y ago
  A radix tree spreads an entry content over several nodes, reusing nodes with similar contents. http://stackoverflow.com/questions/20573231/whats-the-space-complexity-of-a-radix-tree http://stackoverflow.com/questions/20573231/whats-the-space-...
  • 14113 12y ago
    It's still necessarily got a worst case complexity of O(n) - e.g. consider the case where the contents of nodes are perfectly disjoint. In that instance, you'd require O(n) space.
    • judk 12y ago
      With a finite alphabet (which is necessarily the case in complexity theory) the contents of nodes cannot by perfectly disjoint.
      • 14113 12y ago
        Ah yes, you're right - I messed up, and was thinking in terms of strings of symbols, in which case there can be an infinite number. EDIT: Sorry, wait, I was correct all along - as I was talking about the worst case complexity! Consider the case when our alphabet is {A,B}, and I want to store the strings "A" and "B", in that case, I have to use O(n) space, as I'd need at least two nodes for the two strings.
        • SamReidHughes 12y ago
          No. You have to look at infinite subsets of the input space in order to show a counterexample of a Big-O claim. In particular, choose an input for each input size n, let f(n) be the space usage of the radix tree for that input, and show that f(n) is in Theta(n) or at least that it's not o(n).
          • Veedrac 12y ago
            Technically only finite subsets of unbounded size.
            • SamReidHughes 12y ago
              Huh? No? Here the input space is a set of dictionaries. A dictionary is a finite set of strings. A subset of the input space is a set of dictionaries. Finite subsets of the input space are finite sets of dictionaries, thus they have bounded size.
              • Veedrac 12y ago
                Nevermind, I thought you meant something else. To be fair, though, your input doesn't have to be arbitrary subsets of a space. You could require, say, that all strings in the radix tree are about the same size.
                • SamReidHughes 12y ago
                  > You could require, say, that all strings in the radix tree are about the same size. That's just a specification of an arbitrary subset of the input space.
                  • SamReidHughes 12y ago
                    (I misread your last comment :-)
      • SamReidHughes 12y ago
        It doesn't matter though, it's still O(n) worst case (where n is the total size of the data).
• LukeShu 12y ago
  I think your confusion comes from the fact that n does not refer to the number of elements, it refers to the sum of the sizes of all of the elements. Let the number of elements be m, for this discussion. For elements that have a constant/uniform size, this distinction is pointless. However, for things like strings, there can be a large variance in the size. Applying the pigeonhole principle informs us that the radix tree has a lower bound of O(m); but remember that O(n) could be quite a bit larger than that. A radix tree works by only storing one copy of duplicated prefixes of the elements; it still has an upper-bound space complexity of O(n), but the expected complexity is lower than that.
  • SamReidHughes 12y ago
    It depends on how your computer works. If pointers are magic O(1) values, then sure. But if you need as many bits in a pointer as necessary to distinguish the total number of pointers, then you don't get an asymptotic size advantage. Also, using n as the sum of the sizes of all the elements is not normal.
    • LukeShu 12y ago
      > If pointers are magic O(1) values Um... pointers are O(1) size. Usually either a fixed 32 or 64 bits. > then you don't get an asymptotic size advantage. I even said that! I specifically said that it's still O(n) upper bound, but that the expected case is lower than that. Though to be fair, I should have written Ω(m) instead of O(m) when discussing the lower bound. > using n as the sum of the sizes of all the elements is > not normal. 1. I didn't say it was normal; just that in this case, that's what it was referring to. 2. It is though! Worded another way, n is the size of the data being stored.
      • SamReidHughes 12y ago
        >Um... pointers are O(1) size. Usually either a fixed 32 or 64 bits. If you want to talk about asymptotic growth of an algorithm, you need it defined on a machine model that supports infinite memory. Saying that pointers are special O(1) size values are a reasonable way to do that. Another way is to let them be variable size, and include that cost in your measurements. With your 64-bit pointers, you're overpaying that cost. And the transition from 32 bit pointers to 64 bit pointers is an object lesson on the real existence of this logarithmic factor that you'd like to pretend doesn't exist. Edit: also, going with O(1) pointers, the expected asymptotic space usage doesn't mean anything without specifying the probability distribution of dictionaries involved (maybe parameterized on the size n). It's not hard to construct one that changes the outcome.