PRÁCTICA 1A: REPORTE ESCRITO. EXPERIMENTOS Y ANÁLISIS.

PROFESOR: DR. ERIC SADIT TÉLLEZ AVILA

ESTUDIANTE: EDGAR SANTIAGO GONZALEZ MARTINEZ

Introducción

En este reporte comparamos el crecimiento de funciones de costo al escalar el tamaño de entrada $n$, usando la notación $\mathcal{O}$ para describir la cota superior asintótica, es decir, cómo crece el costo cuando $n$ es grande, ignorando constantes y términos menores (Cormen et al., 2009; Van Emden, 2000).

Pares comparados
$\mathcal{O}(1)$ vs $\mathcal{O}(\log n)$
$\mathcal{O}(n)$ vs $\mathcal{O}(n\log n)$
$\mathcal{O}(n^2)$ vs $\mathcal{O}(n^3)$
$\mathcal{O}(a^n)$ vs $\mathcal{O}(n!)$
$\mathcal{O}(n!)$ vs $\mathcal{O}(n^n)$

Además de graficar, probamos distintos rangos de $n$ hasta que cada par de curvas se viera claro y comparable sin saturar el eje, siguiendo recomendaciones introductorias sobre visualización de órdenes de crecimiento (Big-O, s. f.). La idea fue tener gráficas legibles donde se aprecie cuál función crece más rápido.

Para cuantificar diferencias, simulamos tiempos con 1 ns por operación (suponiendo un reloj del orden de 1 GHz; National Institute of Standards and Technology [NIST], s. f.) y construimos una tabla para $n=\{10,100,1000,10000\}$ con $\mathcal{O}(1)$, $\mathcal{O}(\log n)$, $\mathcal{O}(\sqrt n)$, $\mathcal{O}(n^2)$, $\mathcal{O}(2^n)$, $\mathcal{O}(n!)$ y $\mathcal{O}(n^n)$.

Finalmente, discutimos las implicaciones: en la práctica, solo órdenes subcuadráticos (y a veces $\mathcal{O}(n^2)$) escalan para datos masivos; los cúbicos, exponenciales y factoriales se vuelven inviables rápidamente (Cormen et al., 2009; Van Emden, 2000).

import numpy as np
import math
import matplotlib.pyplot as plt

plt.rcParams["figure.figsize"] = (8, 4)
plt.rcParams["axes.grid"] = True

A continuación se presentan las gráficas que comparan las funciones mencionadas seguida de su interpretación.

# Parámetros
N_MAX = 300
LOG_BASE = 2

# Rango y curvas
n = np.arange(1, N_MAX + 1)
logf = (np.log2 if LOG_BASE == 2 else np.log)
y_const = np.ones_like(n, dtype=float)
y_log   = logf(n)

# Plot
plt.figure()
plt.plot(n, y_const, label=r"$O(1)$", color="tab:blue", linewidth=2)
plt.plot(n, y_log,   label=(r"$O(\log_2 n)$" if LOG_BASE==2 else r"$O(\ln n)$"),
         color="tab:green", linestyle="--", linewidth=2)
plt.xlabel("n"); plt.ylabel("f(n)")
plt.title(r"$O(1)$ vs $O(\log n)$")
plt.legend(); plt.tight_layout(); plt.show()

# datos importantes
max_const = y_const.max()
max_log   = y_log[-1]
n_cross   = 2 if LOG_BASE==2 else math.e
y_cross   = 1.0

print(f"max O(1) en n∈[1,{N_MAX}]: {max_const:.0f}")
print(f"max O(log n) en n={N_MAX}: {max_log:.6f}")
print(f"Cruce: O(1) = O(log n) en n = {n_cross:.6g} (En las dos funciones valen {y_cross:.0f})")

max O(1) en n∈[1,300]: 1
max O(log n) en n=300: 8.228819
Cruce: O(1) = O(log n) en n = 2 (En las dos funciones valen 1)

En la Figura de comparación $O(1)$ vs $O(\log n)$ con $1\le n\le 300$, la curva $O(\log_2 n)$ crece muy lentamente: parte cerca de 0 y solo alcanza $\log_2(300)\approx 8.23$, mientras que $O(1)$ se mantiene constante en 1. El punto de cruce ocurre en $n=2$ porque $\log_2 2=1$; desde ahí $O(\log n)$ queda por encima, pero su aumento es de rendimientos decrecientes. Ambas órdenes son “baratos” en todo el intervalo y escalan bien.

n = np.arange(1, 300 + 1)

y_n      = n.astype(float)              # O(n)
y_nlogn  = n * np.log2(n)               # O(n log n)

plt.figure()
plt.plot(n, y_n,     label=r"$O(n)$", color="tab:blue", linewidth=2)
plt.plot(n, y_nlogn, label=r"$O(n\log n)$", color="tab:green", linestyle="--", linewidth=2)
plt.xlabel("n"); plt.ylabel("f(n)")
plt.title(r"$O(n)$ vs $O(n\log n)$")
plt.legend(); plt.tight_layout(); plt.show()

# Datos importantes
N_MAX = int(n[-1])
max_On      = float(y_n[-1])
max_Onlogn  = float(y_nlogn[-1])

# Primer cruce
i_cross = np.where(y_nlogn >= y_n)[0][0]
n_cross = int(n[i_cross])
val_cross = float(y_n[i_cross])

print(f"max O(n) en n={N_MAX}: {max_On:.0f}")
print(f"max O(n log2 n) en n={N_MAX}: {max_Onlogn:.2f}")
print(f"Cruce: O(n) = O(n log2 n) en n={n_cross} (En las dos funciones valen {val_cross:.0f})")

max O(n) en n=300: 300
max O(n log2 n) en n=300: 2468.65
Cruce: O(n) = O(n log2 n) en n=2 (En las dos funciones valen 2)

En la figura $O(n)$ vs $O(n\log n)$ con $1\le n\le 300$, ambas curvas crecen, pero $O(n\log n)$ se separa progresivamente de la lineal: el máximo de $O(n)$ es $300$, mientras que $O(n\log_2 n)$ alcanza $\approx 2468.65$ en $n=300$.

n = np.arange(1, 50 + 1)

y_n2 = n**2
y_n3 = n**3

plt.figure()
plt.plot(n, y_n2, label=r"$O(n^2)$", color="tab:blue", linewidth=2)
plt.plot(n, y_n3, label=r"$O(n^3)$", color="tab:green", linestyle="--", linewidth=2)
plt.xlabel("n"); plt.ylabel("f(n)")
plt.title(r"$O(n^2)$ vs $O(n^3)$")
plt.legend(); plt.tight_layout(); plt.show()

# Datos importantes
N_MAX = int(n[-1])
max_On2 = float(y_n2[-1])
max_On3 = float(y_n3[-1])

# Primer cruce
i_cross = np.where(y_n3 >= y_n2)[0][0]
n_cross = int(n[i_cross])
val_cross = float(y_n2[i_cross])

print(f"max O(n^2) en n={N_MAX}: {max_On2:.0f}")
print(f"max O(n^3) en n={N_MAX}: {max_On3:.0f}")
print(f"Cruce: O(n^2) = O(n^3) en n={n_cross} (ambas valen {val_cross:.0f})")

max O(n^2) en n=50: 2500
max O(n^3) en n=50: 125000
Cruce: O(n^2) = O(n^3) en n=1 (ambas valen 1)

En la figura $O(n^2)$ vs $O(n^3)$ con $1\le n\le 50$, ambas curvas crecen, pero la cúbica se “dispara” mucho antes: el máximo de $O(n^2)$ es $50^2=2{,}500$ mientras que $O(n^3)$ llega a $50^3=125{,}000$. El cruce ocurre en $n=1$ (allí $1^2=1^3=1$); para $n>1$ la curva $O(n^3)$ queda siempre por encima. La razón entre ambas es $O(n^3)/O(n^2)=n$, de modo que la cúbica es $n$ veces más costosa que la cuadrática.

n = np.arange(1, 149 + 1)

y_2n = 2.0**n                         # O(2^n)
y_nf = [math.factorial(int(k)) for k in n]  # O(n!)

plt.figure()
plt.plot(n, y_2n, label=r"$O(2^n)$", color="tab:blue", linewidth=2)
plt.plot(n, y_nf, label=r"$O(n!)$", color="tab:green", linestyle="--", linewidth=2)
plt.yscale("log")
plt.xlabel("n"); plt.ylabel("f(n)")
plt.title(r"$O(2^n)$ vs $O(n!)$")
plt.legend(); plt.tight_layout(); plt.show()

# ----- resumen (solo imprime: máximos y umbral de sobrepaso) -----
N_MAX = int(n[-1])
max_O2n = float(y_2n[-1])    # 2^20 = 1,048,576
max_Onf = float(y_nf[-1])    # 20! ≈ 2.43e18

# Primer n donde n! >= 2^n (no hay igualdad exacta; es el "umbral" de sobrepaso)
bool_ge = np.array(y_nf, dtype=float) >= np.array(y_2n, dtype=float)
i_cross = int(np.argmax(bool_ge))   # índice del primer True
n_cross = int(n[i_cross])

# También mostramos el n anterior para ver el cambio
if i_cross > 0:
    n_prev = int(n[i_cross-1])
    val_prev_factorial = float(y_nf[i_cross-1])
    val_prev_exp       = float(y_2n[i_cross-1])
else:
    n_prev = None

print(f"max O(2^n) en n={N_MAX}:  {max_O2n:.0f}")
print(f"max O(n!)  en n={N_MAX}:  {max_Onf:.2e}")
print(f"Cruce: n! supera a 2^n en n={n_cross} "
      f"(en n={n_cross-1}: n!={val_prev_factorial:.0f} < 2^n={val_prev_exp:.0f})")

max O(2^n) en n=149:  713623846352979940529142984724747568191373312
max O(n!)  en n=149:  3.81e+260
Cruce: n! supera a 2^n en n=4 (en n=3: n!=6 < 2^n=8)

En la figura $O(2^n)$ vs $O(n!)$ (eje $y$ en log) con $1\le n\le 149$ se ve que ambas crecen de forma explosiva, pero el factorial domina muy temprano: el primer cruce ocurre en $n=4$ (en $n=3$ aún $3!=6<2^3=8$, y en $n=4$ ya $4!=24>2^4=16$). Al final del rango, los máximos ilustran la brecha: $2^{149}\approx 7.14\times10^{44}$ frente a $149!\approx 3.81\times10^{260}$. En escala logarítmica, $2^n$ aparece casi como línea recta (porque $\log 2^n=n\log 2$), mientras que $\log(n!)\approx n\log n-n$ tiene pendiente creciente, reflejando que $n!$ es super-exponencial respecto a $n$.

n = np.arange(1, 40+1, dtype=float)
y_nf = np.array([math.factorial(int(k)) for k in n], dtype=float)
y_nn = np.exp(n * np.log(n))          # equivalente a n**n pero evita overflow de int

plt.figure()
plt.plot(n, y_nf, label=r"$O(n!)$", color="tab:blue", linewidth=2)
plt.plot(n, y_nn, label=r"$O(n^n)$", color="tab:green", linestyle="--", linewidth=2)
plt.yscale("log")
plt.xlabel("n"); plt.ylabel("f(n)")
plt.title(r"$O(n!)$ vs $O(n^n)$  (escala log en $y$)")
plt.legend(); plt.tight_layout(); plt.show()

# ----- resumen mini: mínimo, máximo y primer cruce -----
# Mínimos y máximos (ambas crecen en n≥1 ⇒ min en n=1, max en n=n[-1])
imin_nf, imax_nf = int(np.argmin(y_nf)), int(np.argmax(y_nf))
imin_nn, imax_nn = int(np.argmin(y_nn)), int(np.argmax(y_nn))

print(f"min O(n!) : f({int(n[imin_nf])}) = {y_nf[imin_nf]:.0f}   |   max O(n!) : f({int(n[imax_nf])}) = {y_nf[imax_nf]:.0f}")
print(f"min O(n^n): f({int(n[imin_nn])}) = {y_nn[imin_nn]:.0f}   |   max O(n^n): f({int(n[imax_nn])}) = {y_nn[imax_nn]:.0f}")

# Primer cruce: primer n tal que n^n >= n!
mask = y_nn >= y_nf
if np.any(mask):
    i_cross = int(np.argmax(mask))  # índice del primer True
    n_cross = int(n[i_cross])
    print(f"Cruce (primer n con n^n >= n!): n={n_cross}  (n^n={y_nn[i_cross]:.0f}, n!={y_nf[i_cross]:.0f})")
else:
    print("No hay cruce en el rango.")

min O(n!) : f(1) = 1   |   max O(n!) : f(40) = 815915283247897683795548521301193790359984930816
min O(n^n): f(1) = 1   |   max O(n^n): f(40) = 12089258196146223423739578851151290078074592947087867640262164480
Cruce (primer n con n^n >= n!): n=1  (n^n=1, n!=1)

En la figura $O(n!)$ vs $O(n^n)$ (eje $y$ logarítmico) con $1\le n\le 40$, ambas curvas crecen de forma explosiva, pero $O(n^n)$ domina desde el inicio: el primer cruce es en $n=1$ (allí $1^1=1!=1$) y a partir de $n\ge2$ se cumple $n^n>n!$. En el extremo del rango, los máximos ilustran la brecha: $40!\approx 8.16\times10^{47}$ mientras que $40^{40}\approx 1.21\times10^{64}$, es decir, $40^{40}$ es ~(10^{16.17}) veces mayor que $40!$.

Tabla de operaciones y tiempos simulados (1 ns por operación)

A continuación se muestra una tabla con el tiempo estimado (suponiendo 1 ns por operación) para las complejidades $O(1)$, $O(\log n)$, $O(\sqrt n)$, $O(n^2)$, $O(2^n)$, $O(n!)$, $O(n^n)$ y $O(n^{\,n^n})$.

Las filas corresponden a tamaños de entrada $n\in\{10,100,1000,10000\}$; cada columna (por complejidad) incluye Tiempo (1 ns/op).
Usamos $\log_2 n$ para $O(\log n)$; los valores extremadamente grandes se formatean en notación $10^k$ o como $\infty$.

import numpy as np, math, pandas as pd
from math import lgamma
from IPython.display import display

def _log10_ops(kind: str, n: int) -> float:
    k = kind.lower().strip()

    if k == "o(1)":
        return 0.0

    if k in {"o(log n)", "o(logn)"}:
        # log10(log_2 n)
        return math.log10(math.log(n, 2)) if n > 1 else float("-inf")

    if k in {"o(√n)", "o(sqrt n)", "o(sqrtn)"}:
        # n^(1/2)
        return 0.5 * math.log10(n)

    if k in {"o(n^2)", "o(n2)"}:
        # n^2
        return 2 * math.log10(n)

    if k in {"o(2^n)", "o(2**n)"}:
        # 2^n
        return n * math.log10(2.0)

    if k in {"o(n!)", "o(n !)"}:
        # log10(n!)
        return lgamma(n + 1) / math.log(10)

    if k in {"o(n^n)", "o(n**n)"}:
        # n^n
        return n * math.log10(n)

    if k in {"o(n^(n^n))", "o(n**(n**n))", "o(n^(n**n))"}:
        # n^(n^n)
        if n <= 10:
            return (n**n) * math.log10(n)
        else:
            return float("inf")

    raise ValueError(f"Complejidad no soportada: {kind}")


def _fmt_time_from_log10_ns(log10_ns: float) -> str:
    if not np.isfinite(log10_ns):
        return "∞" if log10_ns > 0 else "0"
    if log10_ns < 0:
        return f"{10**log10_ns:.3g} ns"
    if log10_ns < 3:
        return f"{10**log10_ns:.3g} ns"
    if log10_ns < 6:
        return f"{10**(log10_ns-3):.3g} µs"
    if log10_ns < 9:
        return f"{10**(log10_ns-6):.3g} ms"

    log10_s = log10_ns - 9
    if log10_s < 1:
        return f"{10**log10_s:.3g} s"
    if log10_s < 3:
        return f"{(10**log10_s)/60:.3g} min"
    if log10_s < math.log10(3600):
        return f"{(10**log10_s)/60:.3g} min"
    if log10_s < math.log10(86400):
        return f"{(10**log10_s)/3600:.3g} h"
    if log10_s < math.log10(86400 * 365):
        return f"{(10**log10_s)/86400:.3g} días"

    log10_years = log10_s - math.log10(86400 * 365)
    return (f"{10**log10_years:.3g} años"
    if log10_years < 6
            else f"≈ 10^{int(round(log10_years))} años")

n_values = [10, 100, 1000, 10000]

# Complejidades “comunes”
complexities_main = [
    "O(1)",
    "O(log n)",
    "O(√n)",
    "O(n^2)",
    "O(2^n)",
    "O(n!)",]

# Complejidades “extremas”
complexities_extreme = [
    "O(n^n)",
    "O(n^(n^n))",]

all_complexities = complexities_main + complexities_extreme

rows = []
for n in n_values:
    row = {"n": n}
    for comp in all_complexities:
        log10_ops = _log10_ops(comp, n)
        row[comp] = _fmt_time_from_log10_ns(log10_ops)
    rows.append(row)

df_all = pd.DataFrame(rows).set_index("n")

top_level = (["Comunes"] * len(complexities_main) +
             ["Extremas"] * len(complexities_extreme))
bottom_level = all_complexities
df_all.columns = pd.MultiIndex.from_arrays(
    [top_level, bottom_level],
    names=["Grupo", "Complejidad"])
pd.set_option("display.colheader_justify", "center")
display(df_all.style.set_caption("Tiempos (1 ns por operación) para distintas complejidades"))

Tiempos (1 ns por operación) para distintas complejidades

Grupo	Comunes						Extremas
Complejidad	O(1)	O(log n)	O(√n)	O(n^2)	O(2^n)	O(n!)	O(n^n)	O(n^(n^n))
n
10	1 ns	3.32 ns	3.16 ns	100 ns	1.02 µs	3.63 ms	0.167 min	≈ 10^9999999984 años
100	1 ns	6.64 ns	10 ns	10 µs	≈ 10^14 años	≈ 10^141 años	≈ 10^184 años	∞
1000	1 ns	9.97 ns	31.6 ns	1 ms	≈ 10^285 años	≈ 10^2551 años	≈ 10^2984 años	∞
10000	1 ns	13.3 ns	100 ns	100 ms	≈ 10^2994 años	≈ 10^35643 años	≈ 10^39984 años	∞

En la tabla se muestra el por qué la complejidad algorítmica tiene gran importancia. Aun 1 nanosegundo por operación puede ser casi nada, los tiempos pueden aumentar instantáneamente hasta completamente impracticables.

Las complejidades eficientes como $O(1)$, $O(\log n)$ y $O(n)$ son muy escalables: su tiempo apenas aumenta aunque el tamaño de entrada crezca miles de veces. Por ejemplo, para $n=10\,000$, un algoritmo $O(\log n)$ sigue siendo rapidísimo (pues $\log_2 10{,}000 \approx 14$).

En cambio, con $O(2^n)$ y $O(n!)$ el crecimiento es impresionante. Incluso con $n=100$, $2^{100} \approx 1.27 \times 10^{30}$ operaciones; a 1 ns/op son $\sim 4 \times 10^{13}$ años. Para $O(n!)$ los tiempos crecen aún más deprisa.

Conclusión general

Las gráficas y la tabla de "tiempos a 1 ns/operación" ilustran los mismos concepto: cómo la complejidad de un algoritmo determina su viabilidad a medida que crece el tamaño de la entrada ($n$).

Las complejidades subcuadráticas (como $O(1)$, $O(\log n)$ y $O(n)$) son las más convenientes, ya que sus costos se mantienen bajos incluso con entradas muy grandes, lo que las hace ideales para el manejo de datos masivos. La complejidad $O(n^2)$ marca un umbral crítico, siendo aceptable solo para valores de $n$ moderados antes de volverse notablemente lenta.

Por otro lado, las de complejidad exponenciales y factoriales ($O(2^n)$, $O(n!)$) demuestran un crecimiento extremadamente rápido. Aunque pueden ser rápidas para valores diminutos de $n$, se vuelven prácticamente inviables para cualquier entrada real, pasando de segundos a eones con incrementos mínimos en $n$.

Bibliografía

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms (3.ª ed.). MIT Press. (Texto clásico sobre notación asintótica/Big-O).

• “Big-O.” An Open Guide to Data Structures and Algorithms. Enfoque introductorio con definición formal y ejemplos.

• Van Emden, M. H. (2000). Algorithms and Complexity: The Theory and Practice of Computing. Oxford University Press.

• NIST. Fundamentals of Time and Frequency. (1 GHz = $10^9$ ciclos/s).