Does it not? It can't be less than O(n) simply by the pigeonhole principle and it doesn't look like it's more than that.
Does it not? It can't be less than O(n) simply by the pigeonhole principle and it doesn't look like it's more than that.
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.
Also, using n as the sum of the sizes of all the elements is not normal.
> 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.
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.
It would have been correct for the original author to have written that most collections have ϴ(n) space complexity, where radix trees only have O(n) space complexity.
It's common for people to use O when they mean ϴ or Ω. All the original statement was saying is that most collections use as much data as you put in, but some (like radix tree) can use less.
(for fun, if we don't give O(1) pointers: If I'm not mistaken, radix tree has O(m*log(m)+n), Ω(m) space-complexity, which is O(n) iff the average size of an element is ≥ log(m); which it almost certainly would be)
That's stronger than a mere "almost certainly". At least some constant fraction (dependent on the alphabet) would be of size Ω(log m) for some base also dependent on the alphabet, so the average size is also Ω(log m).
I'm not sure how you get your best case, though. It seems to me that the best case has at least Θ(m) nodes since there are m contained strings. The best case for this is each being of minimum size - which is constant size. Each node but the first has a pointer to it of size Ω(log m), so the overall minimum cost is Ω(m log m).
http://stackoverflow.com/questions/20573231/whats-the-space-...
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.
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.
That's just a specification of an arbitrary subset of the input space.