Ejercicio 1

func prob1(a: array de [n] Entero; c: Entero) dev (r: Entero)
var
inf, sup, i: Entero
fin: Lógico
alg
fin := falso //1 OE
inf := 1 //1 OE
sup:=n //1 OE
mientras sup >= inf Y NO fin //2 OE
i := (inf + sup) div 2 //3 OE
si a[i] = c: //2 OE
<> := <> //2 OE
| a[i] > c: //2 OE
sup := i – 1 //2 OE
| otras: //2 OE
inf := i + 1 //2 OE
fsi
fmientras
si NO fin: //1 OE
r := 0 //1 OE
fsi
fin

(a) Calcular el tiempo de ejecución en los casos mejor, peor y medio.

Caso Mejor:

T(n) = 3+1+1+1=5 OE

Caso Peor:

T(n)= 3 + ((sum i=1,n) 2+3+2+2+2) +2+1+1=11n+7

Caso Medio:

T(n) = 3 + 11n/2 + (12n+4)/(n+1)

El 11n/2, sale del cálculo del /IB y el (12n+4)/(n+1) es el /CF

No estoy seguro del que el /CF se tenga que calcular.


(b) Dar las cotas asintóticas para esos tiempos.