GATE 2020 CS Q.6: solution and answer

GATE 2020 · CSQ.6 · 1 mark · MCQ

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

(A)
$Θ (n^{4})$
(B)
$Θ (n^{2})$
(C)
$Θ (n^{2} lo g n)$
(D)
$Θ (n^{3})$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The worst-case time to insert n² elements into an AVL-tree initially holding n elements is Θ(n² log n) — option (C).

Official answer: CSource: Official answer key, GATE 2020 CS (IIT Delhi)

A single insertion into an AVL tree of $m$ nodes costs $Θ (lo g m)$ in the worst case: $Θ (lo g m)$ to search down to the insertion point, plus $O (1)$ rotations to rebalance (each rotation is $O (1)$ ; checking balance factors back up the path is already counted in the $Θ (lo g m)$ search/traversal cost).
We start with $n$ elements and insert $n^{2}$ more elements one at a time, so during this process the tree size $m$ ranges from $n$ (before the first new insertion) up to $n^{2} + n$ (after the last).
For every value of $m$ in this range, $lo g m = Θ (lo g n)$ : at the low end $lo g n$ is trivially $Θ (lo g n)$ , and at the high end $lo g (n^{2} + n) = 2 lo g n + lo g (1 + \frac{1}{n}) = Θ (lo g n)$ , since a constant multiple of $lo g n$ is still $Θ (lo g n)$ .
So every one of the $n^{2}$ insertions costs $Θ (lo g n)$ in the worst case, regardless of exactly where in the sequence it falls.
Total worst-case time $= n^{2}$ insertions $\times Θ (lo g n)$ per insertion $= Θ (n^{2} lo g n)$ .
This matches option (C): $Θ (n^{2} lo g n)$ .

KEY IDEA

Each AVL insertion costs Θ(log m) where m is the current tree size; since the tree size stays between n and n²+n throughout the process, log m is Θ(log n) for every single one of the n² insertions (because log(n²) = 2log n is still just a constant multiple of log n), so the n² insertions together cost Θ(n² log n) — not Θ(n² log(n²)), because Θ absorbs the constant factor of 2.

WATCH OUT FOR

Writing the final tree size as n²+n and concluding the last insertions cost Θ(log(n²)) = Θ(2 log n²) and then sloppily treating the exponent as if it must appear explicitly, sometimes leading to Θ(n² log n²) being (wrongly) simplified to Θ(n⁴) or left as a distinct-looking but numerically identical expression to n² log n — since Θ(log n²) = Θ(2 log n) = Θ(log n) exactly, both forms are the same complexity class, and no additional factor of n or n² should appear.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

GATE 2020 CS Q.6: solution and answer

Answer and solution

More Trees & heaps questions