¿Qué es T(n) y Cómo Calcular la Complejidad Big O a Partir de una Fórmula?
¿Te dieron una fórmula como T(n) y no sabes cómo calcular su complejidad Big O? Aprende paso a paso cómo identificar el término dominante sin complicarte.
¿Qué es T(n) y cómo calcular la complejidad cuando solo te dan una fórmula?
Aprende a leer estas expresiones sin volverte loco
A veces, en clase de algoritmos o en un examen, no te dan código, ni loops, ni listas. Solo te presentan algo como:
T(n) = 0.7n + 9.0n^3.5 + 0.1n^3.75
Y te preguntan:
“¿Cuál es la complejidad Big O?”
Y tú quedas con cara de: ¿esto qué tiene que ver con programar?
En este post te explicamos paso a paso cómo leer y simplificar estas fórmulas sin ahogarte en matemáticas.
¿Qué significa T(n)?
- La letra T representa el tiempo (o el número de operaciones).
- La letra n es el tamaño del problema (generalmente, la cantidad de datos).
- Entonces, T(n) describe cuánto aumenta el tiempo (o los pasos) conforme crece n.
La notación Big O se utiliza para expresar ese crecimiento de manera simplificada, ignorando detalles que no afectan en valores grandes de n.
¿Cómo se resuelve? Pasos básicos
Paso 1: Ignora las constantes (sumas y multiplicaciones)
T(n) = 5n + 100
En Big O, el +100 no importa cuando n es muy grande, ya que se considera constante. Del mismo modo, si tuviéramos 5n, podemos ignorar el factor 5, porque lo relevante es cómo escala n.
El resultado queda:
O(n)