El modelo de Máquina de Acceso Aleatorio (RAM) se define por las siguientes reglas:

1. Operaciones Simples (1 paso cada una):

• ➕ Suma
• ✖️ Multiplicación
• 🔍 Comparación
• 📝 Asignación
• 📞 Llamada a función

2. Operaciones Compuestas:

• 🔁 Bucles: No son operaciones simples, su tiempo depende del número de iteraciones
• 🔧 Subrutinas: Su tiempo depende de la naturaleza del subprograma

3. Acceso a Memoria:

• 💾 Cada acceso toma exactamente 1 paso
• 🎯 Se asume memoria infinita disponible

// Operación simple: 1 paso
x = 5;

// Operación simple: 1 paso
y = x + 3;

// Operación simple: 1 paso
if (x > y) { ... }

// Operación compuesta: n pasos
for (i = 0; i < n; i++) {
    suma += arr[i];  // 2 pasos por iteración (acceso + suma)
}
// Total: 2n pasos

// Operación compuesta: n² pasos
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        matriz[i][j] = 0;  // 1 paso
    }
}
// Total: n × n = n² pasos

Problema: Buscar un elemento en un arreglo desordenado de tamaño $n$

def buscar(arr, objetivo):
    for i in range(len(arr)):
        if arr[i] == objetivo:
            return i
    return -1

# Arreglo ejemplo: [5, 3, 8, 1, 9, 2]

# Buscar: 9

# MEJOR CASO: El elemento está en la primera posición

# arr = [9, 3, 8, 1, 5, 2]

# Pasos: 1 comparación → O(1)

# PEOR CASO: El elemento está al final o no existe

# arr = [5, 3, 8, 1, 2, 9]

# Pasos: n comparaciones → O(n)

# CASO PROMEDIO: El elemento está en una posición aleatoria

# Promedio de posiciones: (1 + 2 + 3 + ... + n) / n = (n+1)/2

# Pasos: ~n/2 comparaciones → O(n)

Conclusión: Aunque el mejor caso es $O(1)$, usamos el peor caso $O(n)$ para garantizar el comportamiento en cualquier situación.

Interpretación de cada notación:

Big Oh (O) - Límite Superior:

• Significa que $f(n)$ crece a lo sumo tan rápido como $g(n)$
• $f(n)$ siempre está por debajo de $c \cdot g(n)$ para $n$ suficientemente grande
• Es como decir “el algoritmo nunca tardará más de esto”

Big Omega (Ω) - Límite Inferior:

• Significa que $f(n)$ crece al menos tan rápido como $g(n)$
• $f(n)$ siempre está por encima de $c \cdot g(n)$ para $n$ suficientemente grande
• Es como decir “el algoritmo tardará como mínimo esto”

Big Theta (Θ) - Límite Ajustado:

• Significa que $f(n)$ crece exactamente a la misma tasa que $g(n)$
• $f(n)$ está entre $c_2 \cdot g(n)$ y $c_1 \cdot g(n)$
• Es la descripción más precisa del comportamiento

Ejemplo práctico:

Dada la función: $f(n) = 3n^2 + 5n + 2$

• $f(n) = O(n^2)$ ✅ (límite superior ajustado)
• $f(n) = O(n^3)$ ✅ (también es límite superior, pero muy holgado)
• $f(n) = \Omega(n^2)$ ✅ (límite inferior ajustado)
• $f(n) = \Omega(n)$ ✅ (también es límite inferior)
• $f(n) = \Theta(n^2)$ ✅ (límite ajustado, el más preciso)

Desarrollo de la sumatoria:

Para un ejemplo con $n = 5$:

Fórmula general:

Este es un ejemplo de la suma de los primeros $n-1$ enteros positivos. La fórmula cerrada conocida es: $T(n) = (n-1)n / 2$

Expansión:

Desarrollando la expresión: $T(n) = (n^2 - n) / 2 = n^2/2 - n/2$

Comparación de Complejidades para Diferentes Tamaños

Leyenda:

• ✅ Práctico: $O(\log n)$, $O(n)$, $O(n \log n)$
• ⚠️ Cuidado: $O(n^2)$ para $n$ grande
• ❌ Impracticable: $O(2^n)$, $O(n!)$

Observaciones:

1. $O(\log n)$ y $O(n)$: Se mantienen prácticas incluso para mil millones de elementos
2. $O(n \log n)$: Excelente escalabilidad (algoritmos de ordenamiento eficientes como Merge Sort, Quick Sort)
3. $O(n^2)$: Aceptable para miles de elementos, problemático para millones
4. $O(2^n)$ y $O(n!)$: Se vuelven impracticables muy rápidamente, incluso para valores pequeños de $n$

Herramientas de Análisis

1. Modelo RAM: Abstracción para análisis independiente del hardware
2. Análisis Asintótico: Estudio del comportamiento cuando $n \to \infty$
3. Notación Big Oh: Lenguaje para expresar complejidad

Tipos de Análisis

• Peor Caso $O(g(n))$: Garantía de límite superior (más usado)
• Mejor Caso $\Omega(g(n))$: Límite inferior
• Caso Promedio $\Theta(g(n))$: Límite ajustado

Principios de Big Oh

1. ✅ Ignorar constantes multiplicativas
2. ✅ Enfocarse en término dominante
3. ✅ Analizar comportamiento para $n$ grande

Complejidades Comunes

O(1)      < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
constante  logarítmica lineal lineal-log  cuadrática exponencial factorial

Regla de Oro

“Algoritmos eficientes escalan. Algoritmos ineficientes colapsan.”