3 ms·
Ok, fair. 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)
by LukeShu 12y ago
Ok, fair.
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)
- Veedrac 12y ago> 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).
- deleted 12y ago[deleted]