1. Notación de Orden

La notación de orden (o notación asintótica) es un tema fundamental en matemática discreta y ciencias de la computación, ya que permite analizar la eficiencia de algoritmos.

La notación de orden describe cómo crece el tiempo de ejecución o el espacio utilizado por un algoritmo en función del tamaño de la entrada ($n$). Es especialmente útil para comparar la eficiencia de diferentes algoritmos cuando $n$ es grande.

Notaciones principales

1. O-grande (O): Límite superior asintótico.
   • Representa el peor caso del crecimiento de una función.
2. Omega-grande (Ω): Límite inferior asintótico.
   • Representa el mejor caso del crecimiento de una función.
3. Theta-grande (Θ): Límite ajustado asintótico.
   • Representa tanto el límite superior como el inferior.

1.1 O-grande (O)

Decimos que $f(n)=O(g(n))$ si existen constantes positivas $c$ y $n_0$ tales que:

$$f(n)≤c⋅g(n) \text{para todo} n≥n_0$$

Esto significa que $g(n)$ es un límite superior para $f(n)$.

Ejemplo: Probar que $f(n)=3n^2+5n+2=O(n^2)$

• Para $n≥1$, tenemos:$3n^2+5n+2≤3n^2+5n^2+2n^2=10n^2$.
• Por lo tanto, $f(n)≤10⋅n^2$ para $n≥1$, y concluimos que $f(n)=O(n^2)$.

1.2 Omega-grande (Ω)

Decimos que $f(n)=Ω(g(n))$ si existen constantes positivas $c$ y $n0$​ tales que:

$$f(n)≥c⋅g(n) \text{para todo} n≥n_0$$

Esto significa que $g(n)$ es un límite inferior para $f(n)$.

Ejemplo: Probar que $f(n)=3n^2+5n+2=Ω(n^2)$

• Para $n≥1$, tenemos:$3n^2+5n+2≥3n^2$.
• Por lo tanto, $f(n)≥3⋅n^2$ para $n≥1$, y concluimos que $f(n)=Ω(n^2)$.

1.3 Theta-grande (Θ)

Decimos que $f(n)=Θ(g(n))$ si existen constantes positivas $c_1$, $c_2$ y $n_0$ tales que:

$$c1⋅g(n)≤f(n)≤c_2⋅g(n) \text{para todo} n≥n_0$$

Esto significa que $g(n)$ es un límite ajustado para $f(n)$.

Ejemplo: Probar que $f(n)=3n^2+5n+2=Θ(n^2)$

• Ya probamos que $f(n)=O(n^2)$ y $f(n)=Ω(n^2)$.
• Por lo tanto, $f(n)=Θ(n^2)$.