What is the worst case time complexity of inserting \(n^2\) elements into an…
2020
What is the worst case time complexity of inserting \(n^2\) elements into an AVL-tree with \(n\) elements initially ?
- A.
\(\Theta (n^{4})\) - B.
\(\Theta (n^{2})\) - C.
\(\Theta (n^{2} \ log \ n)\) - D.
\(\Theta (n^{3})\)
Attempted by 392 students.
Show answer & explanation
Correct answer: C
Key idea: each AVL insertion costs Theta(log m) when the tree has m nodes, and we perform n^2 insertions while the tree grows from n to about n^2.
Initial size = n. Number of insertions = n^2, so final size is Theta(n^2).
Cost of the k-th insertion (k = 0..n^2-1) is Theta(log(n + k)).
Total cost = sum_{k=0}^{n^2-1} Theta(log(n + k)). For all k in this range, log n <= log(n + k) = O(log n), so the sum = Theta(n^2 log n).
Therefore the worst-case running time for inserting n^2 elements into an AVL tree that initially has n elements is Theta(n^2 log n).