Tallerecuacionesrecurrencia.docx

TALLER DE ECUACIONES DE RECURRENCIA 1. Encuentre la ecuación de recurrencia del siguiente algoritmo f(n) if n == 0 f = 1 else f = n * f (n-1) end if end 2. Encuentre la ecuación de recurrencia del siguiente algoritmo f(n) if n == 0 f = 0 else if n == 1 f = 1 else f = f(n-1) + f(n-2) end if end 3. Resuelva las siguientes ecuaciones de recurrencia y determinar el orden de complejidad 1 𝑛≤2 a) 𝑇(𝑛) = { 2 + 𝑇(𝑛 − 2) 𝑛 > 2 1 𝑛=1 b) 𝑇(𝑛) = {1 + 𝑇 (𝑛) 𝑛 > 1 2 0 𝑛=0 𝑛=1 c) 𝑇(𝑛) = { 1 𝑇(𝑛 − 1) + 2𝑇(𝑛 − 2) 𝑛 > 1