How much time does it take one to build the trie

There is a lot of information in the literature which says that the time to search a trie is O(N) where N is the length of the pattern.

Howev开发者_如何学编程er, building the tree will also take some time. To me, let's say there are X words with a total of Y characters.

So then O(Y) is the time (because we have to insert each character). Is this assessment correct (I am usually not correct)

---

So then O(Y) is the time (because we have to insert each character)

Sure, you have to process each input character, and either follow an existing branch or insert a new char.

It can't be faster then O(Y), since you have to look at each input char. There's neither sorting nor any other operation which could make it slower.

---

Wrong. Creating a trie and searching a trie are two different algorithms. One wouldn't build a trie, search it, then throw away the entire data structure.