I am making a study on deduplication with Trie.. In trie, storing the hash values of algorithm(eg-SHA1) and the lookup is done by beam search(say beam width n=2). Now my question what is the time and space complexity for the beam search and on what factor shall I make my heuristic function to choose the nodes. Since I am a basic learner about all these topics, please give your solutions for my doubt.
Thanks in Advance.
Space complexity is beam_width * max_fanout since these are the candidates you generate at each step. Then you need to get the max_fanout best options and repeat the process as many times as you want/can (depends on the height of the tree, or how deep you want to explore).
You can just sort the options and that will give you a time complexity of:
O(depth * beam_width * max_fanout * Log(beam_width * max_fanout)).
Or you can use the quickselect algorithm to identify the base max_fanout candidates, without sorting everything (link). This eliminates the log from the time complexity for a total of: O(depth * beam_width * max_fanout)