2.2.1. Definiciones.
Uso de los órdenes de complejidad: dado un tiempo t(n), encontrar la función f más simple tal que t ? O(f), y que más se aproxime asintóticamente.
Ejemplo. t(n) = 2n2/5 + 6n + 3?·log2 n + 2 ? t(n) ? O(n2)
Relación de orden entre O(..) = Relación de inclusión entre conjuntos.
- O(f) ? O(g) ? O(f) ? O(g) ? Para toda t ? O(f), t ? O(g)
Se cumple que:
- O(c) = O(d), siendo c y d constantes positivas.
- O(c) ? O(n)
- O(cn + b) = O(dn + e)
- O(p) = O(q), si p y q son polinomios del mismo grado.
- O(p) ? O(q), si p es un polinomio de menor grado que q.