6 ms·
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 c
by 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 agoNo. 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 agoTechnically only finite subsets of unbounded size.
- SamReidHughes 12y agoHuh? 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 agoNevermind, 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 :-)