What is the worst case time complexity of inserting n² elements into an AVL-tree with n elements initially?
A.
Θ(n4)
B.
Θ(n2)
C.
Θ(n2logn)
D.
Θ(n3)
Solution:
Time complexity of insertion in an AVL tree = O(logn)
1st element insertion T(1) = O(logn)
2nd element insertion T(n+1)= O(log(n + 1))
3rd element insertion T(n + 2) = O(log(n+2))
.
.
.
(n²)th element insertion = O(log (n+n²))
Total time complexity
= O(logn) + O(log(n+1)) + O (log(n+2)) +. . .+ O(log(n+n²))
= O(log(n*(n+1)*(n+2)*. . .(n+n2)))
= O(log(nn2)
= O(n2logn)