https://www.cs.us.es/~jalonso/cursos/i1m-19/temas/tema-28.html

1.1 Definición de O(g)

• La función f pertenece a la clase de complejidad de g (en símbolos, f ∈ O(g)) si existe un c y un n₀ tales que para todo n ≥ nₒ se tiene que |f(n)| ≤ c|g(n)|
• f ∈ O(g) syss ∃c∃nₒ∀n(n ≥ n₀ → |f(n)| ≤ c|g(n)|)
• f ∈ O(g) syss

limsup   |f(x)/g(x)| < ∞
x → ∞

• Intuitivamente, sólo se considera el término más importante y se ignoran los factores constantes.
• Ejemplos:
  • 3n²+5n-7 ∈ O(n²).
  • O(2g(n)) = O(g(n))
  • O(log n) = O(ln n)
  • O(3n²+5n-7) = O(n²)
  • O(n²) ⊂ O(n³)
  • O(2ⁿ) ⊂ O(3ⁿ)

1.2 Propiedades

• Si g ∈ O(f) y h ∈ O(f), entonces g+h ∈ O(f)
• Si f ∈ O(g) y g ∈ O(h), entonces f ∈ O(h)
• f+g ∈ O(max(f,g))
• O(f+g) = O(max(f,g))
• Si f ∈ O(f') y g ∈ O(g'), entonces f+g ∈ O(f'+g')
• Si f ∈ O(f') y g ∈ O(g'), entonces f.g ∈ O(f'.g')
• Si f ∈ O(g) y a ∈ ℜ⁺-{0}, entonces a.f ∈ O(g)
• Si f ∈ O(g) y n ≥ 1, entonces fⁿ ∈ O(gⁿ)

2.1 Principales órdenes de complejidad

Orden	Nombre
O(1)	constante
O(log n)	logarítmica
O(n)	lineal
O(n log n)	casi lineal
O(n²)	cuadrática
O(n³)	cúbica
O(a^n)	exponencial