2.2.4. Notaciones condicionales.
En algunos casos interesa estudiar el tiempo sólo para ciertos tamaños de entrada.
Ejemplo. Algoritmo de búsqueda binaria: Si N es potencia de 2 el estudio se simplifica.
Orden condicionado de f(n): O(f | P)
Dada una función f: N ? R+, y P: N ? B, llamamos orden de f según P (o condicionado a P) al conjunto:
O(f | P)= { t: N ? R+ / ? c ? R+, ? n0 ? N, ? n ? n0:
De igual forma, tenemos ?(f | P) y ?(f | P).
O(f) = O(f | true). Para cualquier f y g, f ? O(g | false).