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

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