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.
Compare 3n + 4 contra n². Al principio la recta gana. ¿Desde qué n se cumple 3n + 4 ≤ n² y no se vuelve a romper?
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.
La misma cacería con otra función. ¿Qué c y qué k propone?
Para 2n + 10 ∈ O(n) se proponen cuatro parejas de testigos. Tres demuestran el teorema; una no lo demuestra jamás. ¿Cuál?