[marcela]

Saludos.

Tengo un algoritmo de búsqueda binaria al que le tengo que calcular el tiempo de ejecución para el mejor y el peor caso, esto contando las operaciones elementales.



El problema es que para el peor caso, a la hora de calcular me sale esto:

\( \displaystyle T(n)=2+\sum_{i=1}^n (1+3+2+2+2)+1+1=10n+4 \)

pero la respuesta del libro me dice que es:

\( 10 \log(n) +4 \) y no entiendo porqué sale el logaritmo, cómo puedo yo deducir cuándo se necesita logaritmo y cuándo no.

Disculpa por no poner acentos, mi teclado no me lo permite.

[pierrot]

Recién leo este hilo, y veo que planteaste esta duda hace ya varios días.

Tal vez sea tarde, pero por si aún no lo es, observa que el peor caso se da cuando el entero c no pertenece al arreglo a (o bien está en uno de sus extremos).

En dicho caso el cuerpo del while se ejecuta un número \( k \) de veces, tal que \( 2^k=n \) siendo \( n \) la cantidad de elementos del vector. ¿Por qué se cumple esto?

Fíjate que inicialmente inf=1 y sup=n, o sea, buscamos en un rango de longitud \( n \). Luego de ejecutada la primer iteración, buscamos en un rango de longitud \( n/2 \); luego de ejecutada la segunda iteración en un rango de longitud \( n/4 \) y así sucesivamente.

¿Y cuándo se detiene el algoritmo? El algoritmo se detiene cuando nuestro rango de búsqueda es uno, es decir, cuando inf=sup. A partir de ahí:

\( \dfrac{n}{2^i}=1 \)

lo que conduce a \( i=\log_2(n) \).