Regla del limite - andres726127/An-lisis-de-Algoritmos GitHub Wiki

package comprobacionb1;
public class ComprobacionB1 {

    public static double f1(int n) {
        return Math.pow(n, 3) + 9 * n * n * Math.log(n);
    }

    public static double g1(int n) {
        return n * n * Math.log(n);
    }

    public static double n2(int n) {
        return n * n;
    }

    public static double f2(int n) {
        return Math.pow(2, n);
    }

    public static double g2(int n) {
        return Math.pow(2, 2 * n); // equivalente a (2^n)^2
    }

    public static void main(String[] args) {
        System.out.printf("%-5s %-15s %-15s %-15s %-15s %-15s\n", "n", "f1(n)", "g1(n)", "f1/g1", "f1/n^2", "f2/g2");

        for (int n = 2; n <= 100; n *= 2) {
            double f1 = f1(n);
            double g1 = g1(n);
            double f2 = f2(n);
            double g2 = g2(n);
            double n2 = n2(n);

            System.out.printf("%-5d %-15.2f %-15.2f %-15.4f %-15.4f %-15.8f\n",
                    n, f1, g1, f1 / g1, f1 / n2, f2 / g2);
        }
    }
}

Análisis de Complejidades Asintóticas

Funciones dadas:

• ( f(n) = n^3 + 9n^2 \log(n) )
• ( g(n) = n^2 \log(n) )
• ( h(n) = n^2 )
• También se analiza:
  • ( f(n) = 2^n )
  • ( g(n) = 2^{2n} )

---

Parte 1: Comparación entre ( f(n) = n^3 + 9n^2 \log(n) ) y otras funciones

¿Pertenece ( f(n) \in O(n^2 \log(n)) )?

• No.
• El término dominante de ( f(n) ) es ( n^3 ), que crece más rápido que ( n^2 \log(n) ).
• Por lo tanto, f(n) no pertenece a O(n² log(n)).
• Resultado experimental: la razón f(n) / g(n) tiende a infinito conforme crece n.

¿Pertenece ( f(n) \notin O(n^2) )?

• Correcto.
• Nuevamente, ( n^3 ) domina y crece más que ( n^2 ).
• Resultado experimental: f(n) / n^2 tiende a infinito.
• Por lo tanto, f(n) no pertenece a O(n²).

---

Parte 2: Comparación entre funciones exponenciales

¿Pertenece ( f(n) = 2^n \in O(2^{2n}) )?

• Sí.
• ( 2^n \ll 2^{2n} = (2^n)^2 ).
• La función ( f(n) ) crece exponencialmente más lento que ( g(n) ).
• Resultado experimental: la razón f(n) / g(n) tiende a 0 conforme crece n.

¿Pertenece ( g(n) = 2^{2n} \in O(2^n) )?

• No.
• ( g(n) ) crece mucho más rápido que ( f(n) = 2^n ).
• Resultado experimental: la razón g(n) / f(n) tiende a infinito, lo que significa que g(n) no pertenece a O(f(n)).

---

Conclusión

La experimentación con diferentes valores de n confirma los resultados teóricos.
El uso de cocientes como f(n)/g(n) o f(n)/n^2 ayuda a visualizar la relación de crecimiento y verificar si las funciones pertenecen o no a una cota superior.