Algorithm Question: Given the balanced binary trees T_1 and T_2, which contain m

Question

Algorithm Question:

Given the balanced binary trees T_1 and T_2, which contain m and n elements respectively, we want to determine whether they have some particular key in common. Assume an adversarial sequence that placed the m and n items into the two trees.

(B) Now suppose our algorithm first allocates a new hash table H_1 of size m (assume H_1 uses a uniform hash function) and then inserts every key in T_1 into H_1 during a traversal of T_1. Then we traverse the tree T_2 and search for whether the key of each node traversed already exists in H_1. Give the asymptotic running time of this algorithm in the "average case". Justify your answer.

Explanation / Answer

Time taken for traversal of a balanced binary search tree T_1 = O(m)

Each insertion to hash table will take O(1) given uniform hash function with hastable of size = m

Now We will traverse T_2 and check each key of node in H_1, lookup in H_1 will be O(1) as it has a uniform hash fnction.

Now if look up contain same value means key is found

so if there is a common key, we will find it in worst case of O(n) (after traversing tree T_2 completely)

So overall time:

Building hash H_1: O(m)

Checking common entry: O(n)

so Time will be O(m+n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.