Question

What is the worst case time complexity of inserting n² elements into an AVL-tree with n elements initially?

Accepted Answer

The correct answer is (C) Θ(n² log n). An AVL tree stays balanced, so each insertion into a tree of current size m costs O(log m). Inserting n² elements grows the tree from n to about n²+n ≈ n² elements, and every single one of those n² insertions costs O(log(n²)) = O(log n) in the worst case (using the final, largest size as an upper bound on every insertion's cost). Total cost = n² × O(log n) = Θ(n² log n).

Explanation