2.4. Ejemplos.

• Ejemplo 3. Dada la siguiente ecuación de recurrencia, con a, b, c y p ? R+ y d, n0 ? N+:

f(n) =

Demostrar que: a < dp ? f ? O(np)

a = dp ? f ? O(np·log n)

a > dp ? f ? O(nlog d a)

• Ejemplo 4. Calcular el número de instrucciones de asignación del siguiente algoritmo.

procedure Otro (n: integer): integer;

for i:= 1 to n do

M[i]:= M[i] + 1;

if iɬ then Otro(n-4)

c Si n ? n0

a·f(n/d) + bnp Si n > n0

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica