Scribd
Cargar
37 vistas1 página

Algoritmos Recursivos: Ejercicios y Soluciones

Cargado por

juan godoy
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
37 vistas1 página

Algoritmos Recursivos: Ejercicios y Soluciones

Cargado por

juan godoy
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Cátedra: Desarrollo Sistemático de Programas Tema: Algoritmos Recursivos

Tema: Algoritmos Recursivos

Trabajo Práctico Nº 2

1) Demostrar usando el método de sustitución que la recurrencia

1 si n = 1
T(n) = { }
T( n / 5 ) + T( 3n / 4 ) + n en caso contrario

Es ø (n)

2) Resolver las siguientes recurrencias usando el método iterativo y aplicando el teorema


maestro cuando corresponda. Para todas las recurrencias T(n) = 1 si n = 1

a) T(n) = 3T( n/2 ) + n2


b) T(n) = 3T( n - 1) + ( 1 / n )
c) T(n) = \/n + n
d) T(n) = 2T( n / 2 ) + ( 3n – 1 )
e) T( n ) = 5 T ( n / 2 ) + n2
f) T( n ) = (1/2) T ( n / 2 ) + n2
g) T( n ) = T ( n + 2 ) + n2 + 3
h) T( n ) = T ( n + 3 ) + n2 + 2
i) T( n ) = T ( 2 n ) + 2 n + 2
j) T( n ) = T ( 3 n ) + 3 n + 3
k) T( n ) = (1/4) T ( n - 2 ) + n
l) T( n ) = (1/3) T ( n - 3 ) + n
m) T( n ) = (1/2) T ( n - 4 ) + n
n) T( n ) = 2 T ( n / 5 ) + n3
o) T( n ) = 7 T (n - 1) + n /5 +6

Año: 2.023 Trabajo Práctico Nº2 Página: 1

También podría gustarte