3 ms·
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
by 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 agoWith a finite alphabet (which is necessarily the case in complexity theory) the contents of nodes cannot by perfectly disjoint.
- 14113 12y agoAh 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 :-)
- SamReidHughes 12y agoIt doesn't matter though, it's still O(n) worst case (where n is the total size of the data).