PUERTA | PUERTA CS 2020 | Pregunta 51

En un árbol de búsqueda binario balanceado con n elementos, ¿cuál es la complejidad de tiempo en el peor de los casos de informar todos los elementos en el rango [a,b]? Suponga que el número de elementos informados es k.
(A) Θ(log n)
(B) Θ(log(n)+k)
(C) Θ(k log n)
(D) Θ(n log k)

Respuesta: (B)
Explicación:

1. Complejidad de tiempo para verificar si el elemento ‘a’ en el árbol de búsqueda binario balanceado dado = O (log n)
2. Complejidad de tiempo para verificar si el elemento ‘a’ en el árbol de búsqueda binario balanceado dado = O (log n)
3. Ahora, la complejidad del tiempo para atravesar todos los elementos en el rango [a, b], esos elementos se ordenarán en orden = θ (k)

Por lo tanto, la complejidad temporal total será,

= Θ(log(n)) + Θ(log(n)) + Θ(k)
= Θ(2(log(n))+k)
= Θ(log(n)+k) 

La opción (B) es correcta.

Cuestionario de esta pregunta