Question

Design an algorithm (write in pseudo code) which takes less than Θ(n) to search an entry (name of a person) in a telephone directory. Analyze this algorithm for its worst-case input situation. Make necessary assumptions to simplify your comparisons. If you don’t know what is a telephone directory, check out this link https://en.wikipedia.org/wiki/Telephone_directory

Answer 1

The solution of this problem is "Trie".Trie is tree kind of searching data structure.Trie is also known as digital tree,or prefix tree.specially the node of this kind of tree stores the "string".In trie all the descendant node have string associated with them and have the common prefix of this string.And root node will be associated with the empty string.Value may be associated with inner nodes ,and key of interest.

Pseudo code:

import Data.Map
 
data Trie b = Trie { value    :: Maybe b,
                     childs :: Map Char (Trie b) }

Code for lookup:

search :: String -> Trie b -> Maybe b
search []     val = value val
search (k:ks) val = do
  cval <- Data.Map.lookup k (child val)
  search ks cval

?Suppose you write the code in python:

def search(searchnode, key):
    for ch in key:
        if ch in searchnode.child:
            searchnode = searchnode.child[ch]
        else:
            return None
    return node

The lookup time complexity in O(n) in worst case where n is the length of searching string.which faster than hash table.so the average and the best time complexity will be always lesser than o(n).below is the one example picture of tree.