Gate2020 cs Q33

0. What is the worst case time complexity of inserting n² elements into an AVL Tree with n elements initially?

Answer
Comment
Array

Option : A
Explanation :
Insertion of an element into AVL requires O(log n) time.
To insert an element
1. Find the position, where to insert
2. After insertion, to satisfy AVL properly, we may need to perform rotation.
So, (1) take ‘log n time’ and (2) take ‘log n’ time.
Total time for inserting one element into AVL tree is
log n + log n = 2 log n ⇒ O (log n).
Now, To insert n² elements ⇒ n² log n
⇒ O(n² log n)

Forgot your password?

I agree with the Terms.