📌 ¿Qué son las Notaciones Asintóticas?

Las notaciones asintóticas nos ayudan a describir cómo crece el tiempo de ejecución o el uso de memoria de un algoritmo a medida que aumenta el tamaño de la entrada (n).

✅ Nos permiten comparar algoritmos sin depender de la velocidad del hardware o del lenguaje de programación.

📌 Ejemplo:
Si un algoritmo toma 1 segundo para n = 1000 y 4 segundos para n = 2000, significa que su tiempo de ejecución no es constante, sino que crece con n.

Para describir la eficiencia de un algoritmo usamos tres tipos de notaciones:

• O(n) → Límite superior (el peor caso).
• Ω(n) → Límite inferior (el mejor caso).
• Θ(n) → Caso ajustado (cuando el peor y el mejor caso son iguales).

📌 O(n) – Notación O grande (cota superior)

La notación O (O grande) representa el peor caso de un algoritmo. Nos dice cómo crece el tiempo de ejecución en función de n.

Ejemplo: Búsqueda Lineal (O(n))

Si tenemos un array de n elementos y buscamos un número, en el peor caso recorremos todo el array.

1public class LinearSearch {
2    public static boolean search(int[] arr, int target) {
3        for (int num : arr) {
4            if (num == target) {
5                return true;
6            }
7        }
8        return false;
9    }
10}

📌 Conclusión: En el peor caso, debemos recorrer los n elementos, por lo que O(n) significa que el tiempo de ejecución crece linealmente.

📌 Ω(n) – Notación Omega (cota inferior)

La notación Ω (Omega) representa el mejor caso de un algoritmo. Nos dice el mínimo tiempo posible que puede tomar.

Ejemplo: Búsqueda Lineal (Ω(1))

Si el elemento buscado está en la primera posición, lo encontramos de inmediato.

1public class BestCaseSearch {
2    public static boolean search(int[] arr, int target) {
3        if (arr[0] == target) return true; // Mejor caso: Primer elemento
4        for (int num : arr) {
5            if (num == target) return true;
6        }
7        return false;
8    }
9}

📌 Conclusión: En el mejor caso, encontramos el elemento en la primera posición, lo que nos da Ω(1).

📌 Θ(n) – Notación Theta (cota ajustada)

La notación Θ (Theta) indica que el tiempo de ejecución siempre crece al mismo ritmo, sin importar el caso.

• Ejemplo: Sumar los elementos de un array
  • Siempre recorremos todos los elementos.
  • El peor y mejor caso son iguales.

1public class SumArray {
2    public static int sum(int[] arr) {
3        int total = 0;
4        for (int num : arr) {
5            total += num;
6        }
7        return total;
8    }
9}

📌 Conclusión: En este caso, siempre recorremos todo el array, por lo que el mejor y peor caso son iguales, lo que da Θ(n).

📌 Comparación de Notaciones