Taller De Algoritmos

1. Desarrolle los siguientes ejercicios del [Cormen09]

(a) 3.1-1 Let f (n) and g(n) be asymptotically nonnegative functos. Using the basic definition of Θ-notation, prove that max(f (n), g(n)) =Θ(f (n) + g(n)). Respuesta: supongamos que max(f (n), g(n)) = h(n) y el min(f (n), g(n)) = k(n) osea (f (n) + g(n)) = (h(n) + k(n) ∀(n ≥ n0 ) entonces: ∃c1 y c2 | ∀(n > n0 ) y c1 , c2 > 0 se cumple que0 ≤ c1 (f (n) + g(n)) ≤ h(n) ≤ c2 (f (n) + g(n))

dividiendo todo por h(n) tenemos que: f (n) + g(n) f (n) + g(n) ) ≤ 1 ≤ c2 ( ) h(n) h(n)

0 ≤ c1 (

ahora tomamos un n0 arbitrario por ejemplon0 = 1 como g(n) < f (n) supongamos que g(n) ≈ f (n) ≈ h(n) entonces entonces tenemos que: f (n) ≤1 h(n) g(n) ≤1 h(n) g(n) f (n) ≈1y ≈1 h(n) h(n)

0≤ 0≤

0 ≤ 2c1 ≤ 1 ≤ 2c2

1 y c2 ≥ 1 para todon > 1 de igual forma para 2 max(f (n), g(n)) = g(n) repitiendo el mismo proceso llegariamos al mismo resultado entonces para cumplir esa desigualdad c1 ≤

1

(b) 3.1-4 Is 2n+1 = O(2n )? Is 22n =O(2n )? tenemos: 2n+1 = O(2n ) =⇒ 2n+1 = 2 ∗ 2n = O(2n ) por definicion: ∀(n > n0 )∃(c > 0) | 2 ∗ 2n ≤ c ∗ 2n podemos escoger n0 = 1 y un c ≥ 2 osea c = 3 para que se cumpla. tenemos: 22n = O(2n ) =⇒22n = 2n ∗ 2n = O(2n ) por definicion: ∀(n > n0 )∃(c > 0) | 2n ∗ 2n ≤ c ∗ 2n dividiendo todo por 2n tenemos: 2n ≤ c lo cual es falso ya que no existe un c lo suficiente mente grande que culpla esadesigualdad.

(c) 3.2-3 Prove equation (3.19). Also prove that n! = ω(2n ) and n! = o(nn ) (d) 4.4-7 Draw the recursion tree for T (n) = 4T ( n/2 ) + cn, where c is a constant, and provide a tightasymptotic bound on its solution. Verify your bound by the substitution method. = cn cn

cn 2

cn 2

cn 2

cn 2

=

2cn

cn 4

cn 4

c.n .4 .

c.n .4 .

. . .

. . .

c.n .4 .c.n .4 .

cn 4

cn 4

=

4cn

. . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .

. . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . ....