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.

With a finite alphabet (which is necessarily the case in complexity theory) the contents of nodes cannot by perfectly disjoint.

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.

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).

Technically only finite subsets of unbounded size.

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.

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.

> 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.

(I misread your last comment :-)