How tries are efficient?

#1

basically if we simply transverse the paragraph word by word and compare each word with the required ,we can break the loop once we are done i.e no need to transverse the whole paragraph but in tries we have to transverse the whole paragraph once even if the required word is the first word in the paragraph

#2

yeah , you are right , but what about the case when you have multiple queries , i.e. you have many words you want to check if it is present in the paragraph or not , In that case you have to traverse the whole array each time in the worst case.
Let me explain by giving you an example : -

let’s say you have a paragraph containing n words , and lets say you have n querries of words you intend to check if the word is in the paragraph or not , if we follow your approach then we will have to traverse whole paragraph for every querry and it will take n(no of words)*n(no of querries) operations i.e O(n^2) time complexity in the worst case .

But now let’s see what happens if you build a trie
Now , for building a trie it will take O(n * keylength) (note keylength is the size of word to be searched which is always less than 100 as longest word in english comprises of 45 words)
and for every query trie take o(keylength) time so for n querries it will take o(n * keylength)
which is approx O(n)

In case of any doubt feel free to ask :slight_smile:
mark your doubt as RESOLVED if you got the answer