← Volver a los ejercicios

Cazar testigos

Decir que T(n) ∈ O(g(n)) es prometer un techo: existen una constante c y un punto de arranque k tales que T(n) ≤ c·g(n) para todo n ≥ k. Aquí la promesa se pone a prueba con números.

1. El experimento

Compare 3n + 4 contra n². Al principio la recta gana. ¿Desde qué n se cumple 3n + 4 ≤ n² y no se vuelve a romper?

2. Testigos para 3n + 4 ∈ O(n)

Ahora el techo es una recta: c·n. Proponga una pareja (c, k) y el comprobador la acepta o le muestra dónde falla. Meta: encontrar dos parejas distintas que sirvan.

c = k =
Pista para arrancar: pruebe primero una c que no supere a 3 y mire qué contesta el comprobador.

3. Ahora usted: 5n + 5 ∈ O(n)

La misma cacería con otra función. ¿Qué c y qué k propone?

c = k =

4. La pareja que no sirve

Para 2n + 10 ∈ O(n) se proponen cuatro parejas de testigos. Tres demuestran el teorema; una no lo demuestra jamás. ¿Cuál?