Given the balanced binary trees T_1 and T_2, which contain m and n elements resp

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.

Plase give a descriptive answer. Thank you. Its one question.

Explanation / Answer

The average case running time of this algorithm is theta(m+n)...

Where m the number of nodes in T_1

Where n is the number of nodes in T_2

Justification :

Step 1: to Traverse m nodes in T_1 ,takes O( m ) time and inserting into hash table takes constant time

Step2 : to traverse n nodes in T_2, takes O(n) time, to searching in hash table also takes constant time..

Henceforth, The Total complexity, would be O(n+m)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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