PUERTA | PUERTA CS 2020 | Pregunta 16

¿Cuál es la complejidad de tiempo en el peor de los casos de insertar n ² elementos en un árbol AVL con n elementos inicialmente?
(A) Θ(n ⁴ )
(B) Θ(n ² )
(C) Θ(n ² log n)
(D) Θ(n ³ )

Respuesta: (C)
Explicación: Dado que el árbol AVL es un árbol equilibrado, la altura es O(log n). Entonces, la complejidad del tiempo para insertar un elemento en un árbol AVL es O (log n) en el peor de los casos.

Nota:

Every insertion of element:
Finding place to insert = O(log n)
If property not satisfied (after insertion) do rotation = O(log n)

So, an AVL insertion take = O(log n) + O(log n) = O(log n) in worst case. 

Ahora, dado que el elemento n ² debe insertarse en el árbol AVL dado, por lo tanto, la complejidad de tiempo total será O (n ² log n).

Método alternativo: Complejidad temporal en el peor de los casos,

1st insertion time complexity = O(log n)
2nd insertion time complexity = O(log(n+1))
.
.
.
n2th insertion time complexity = O(log(n + n2)) 

Entonces, la complejidad del tiempo total será,

= O(log n) +  O(log n+1)) + .... +  O(log(n + n2))
= O(log n*(n+1)*(n+2)*...(n+n2))
= O(log nn2)
= O(n2 log n) 

La opción (C) es correcta.

Cuestionario de esta pregunta