2.2.5. Cotas de complejidad frecuentes.
Algunas relaciones entre órdenes frecuentes.
O(1) ? O(log n) ? O(n) ? O(n·log n) ? O(n·(log n)2) ? O(n1.001...) ? O(n2) ? O(n3) ? ... ? O(2n) ? O(n!) ? O(nn)
¿Qué pasa con las omegas? ¿Y con los órdenes exactos?
El orden de un polinomio anxn+...+a1x+a0 es O(xn).
?1 = n ? O(n); ?i = n(n+1)/2 ? O(n2); ?im ? O(nm+1)
Si hacemos una operación para n, otra para n/2, n/4, ..., aparecerá un orden logarítmico O(log2 n).
Los logaritmos son del mismo orden, independientemente de la base.