2.3.3. Cambio de variable.
Los órdenes que obtenemos son condicionados a que se cumplan las condiciones del cambio. t(n) ? O(f|P(n))
¿Cómo quitar la condición?
Teorema. Sea b un entero ?2, f: N ? R+ una función no decreciente a partir de un n0 (f es eventualmente no decreciente) y f(bn) ? O(f(n)) (f es b-armónica) y t: N ? R+ eventualmente no decreciente. Entonces, si t(n) ? ?(f(n) | n=bk) se cumple que t(n) ? ?(f(n)).
Quitar la condición del ejemplo 1. t(n) ? ?(n·log n|n=2k)
- n·log n, es eventualmente no decreciente y 2-armónica.
- t(n) es eventualmente no decreciente.