Complejidad temporal
Cómo escala el tiempo de ejecución con el tamaño de entrada (Big O).
Time complexity measures how the execution time of an algorithm scales as input size (n) increases. It's expressed using Big O notation, which describes the upper bound (worst-case) growth rate.
Common time complexities:
- O(1) Constant: Same time regardless of input (array index access)
- O(log n) Logarithmic: Halves problem each step (binary search)
- O(n) Linear: Time proportional to input (single loop)
- O(n log n) Linearithmic: Efficient sorting (mergesort, quicksort)
- O(n²) Quadratic: Nested loops (bubble sort)
- O(2ⁿ) Exponential: Doubles each step (naive recursion)
Big O focuses on dominant terms as n→∞, ignoring constants and lower-order terms.
graph LR
Center["Complejidad temporal"]:::main
Pre_algorithm["algorithm"]:::pre --> Center
click Pre_algorithm "/terms/algorithm"
Rel_space_complexity["space-complexity"]:::related -.-> Center
click Rel_space_complexity "/terms/space-complexity"
Rel_algorithm["algorithm"]:::related -.-> Center
click Rel_algorithm "/terms/algorithm"
Rel_big_o_notation["big-o-notation"]:::related -.-> Center
click Rel_big_o_notation "/terms/big-o-notation"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧒 Explícalo como si tuviera 5 años
Imagina contar cuántos pasos toma encontrar un juguete. Si siempre lo encuentras inmediatamente, eso es O(1). Si revisas cada caja una por una, eso es O(n). ¡La complejidad temporal nos dice cuánto más tardan las cosas cuando tenemos más!
🤓 Expert Deep Dive
El análisis amortizado promedia costos sobre secuencias. Big-Θ (límite ajustado), Big-Ω (límite inferior) complementan Big-O. El teorema maestro resuelve recurrencias T(n) = aT(n/b) + f(n). El rendimiento práctico puede diferir de Big-O debido a factores constantes y efectos de caché.