Now that we've seen the basic operations on how to work with a TRIE, we shall now see the space and time complexities in order to get a real feel of how good a TRIE data structure is. Lets take the two important operations INSERT and SEARCH to measure the complexity.
INSERT operation first. Lets always take into account the worst case timing first and later convince ourselves of the practical timings. For every Node in the TRIE we had something called as Collection
Having these in mind, for inserting a word of length 'k' we need (k * 26) comparisons. By Applying the Big O notation it becomes O(k) which will be again O(1). Thus insert operations are performed in constant time irrespective of the length of the input string (this might look lik an understatement, but if we make the length of the input string a worst case maximum, this sentence holds true).
Same holds true for the search operation as well. The search operation exactly performs the way the insert does and its order is O(k*26) = O(1).
10 comments:
Hey, How come O(k) became O(1) in the above explanation? Could you pls clarify me?
@chiranjeevi:
To understand this, you will have to have a deep knowledge on what "Order" means. The Big O notation is used to tell how the complexity increases according to the increase in the input space. For TRIE ADT, the input space is the number of words that we use. Assume we have 10 words, the insert operation will take a total of its word length multiplied by the 26 letters in the linked list. Which will be equal to k*26. Applying Big O we have O(k*26) = O(1). The reason is this does not depend upon the increase in the number of words that the TRIE is going to have.
Even if the TRIE has a billion words, the insert operation will take a constant time of k*26 which is irrespective of 'n'. So, if you plot a curve you could see that its constant and in Big O terms, it is called as O(1) or constant time insertion.
Hope this helps.
Thankyou very much for the clarification. Now, I got it.
@chiranjeevi: Happy to help!
is ther c code for this..
Very good explanation. To the point and in Java :)
Very well explained!! great post.
Thanks Ramya for stopping by!
Can you give me any idea how can i compare 2 tries?
Excellent job. You should write a book on all data structures. Another thing is that you wrote the algo..after giving the code for insert and search. If algo could have been discussed first, it would have been a bit easier to understand for new bees like me.
Anyways, it was very good.
Thanks.
Post a Comment