Ad

Dictionary Using Balanced BST Lookup Time Complexity

I was going through an article in geeksforgeeks on how to implement dictionary using balanced BST and found this line:

If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree.

I didn't understand how this would be O(M*logn), given balanced BSTs always maintain a max height of O(logn), shouldn't this be (logn)?

Ad

Answer

This quote is taken from a context of searching words in a dictionary:

Trie is an efficient data structure for searching words in dictionaries, search complexity with Trie is linear in terms of word (or key) length to be searched. If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using trie, we can search the key in O(M) time. So it is much faster than BST.

In a BST these words would be stored such that one node gets one word.

Although in a balanced BST of 𝑁 nodes you need to visit O(log𝑁) nodes to find the targeted value in the worst case, it will also take time to compare a node's string with the target string. As the maximum length of a word is given as 𝑀, the worst case time complexity for each individual string comparison is O(𝑀). As such a comparison happens at each visited node, this gives a total complexity of O(𝑀log𝑁).

Ad
source: stackoverflow.com
Ad