Complejidad computacional

La función de complejidad de un algoritmo es una función $f : \N \to \R_{\geq 0}$ tal que $f(n)$ es a cantidad de operaciones elementales que realiza el algoritmo en el peor caso para una entrada de tamaño $n$.

Notación Big O

Si $f$ y $g$ son dos funciones decimos que $f \in O(g)$ si existen $c \in \R$ y $n_0 \in \N$ tales que

$$ f(n) \leq c \cdot g (n) \quad \forall n \geq n_0 $$

Intuitivamente $f \in O(g)$ si $g(n)$ "le gana" a $f(n)$ para valores grandes de $n$.

Utilizamos la notación $O$ para expresar la función de complejidad computacional $f$ de un algoritmo.

• Si $f \in O(n)$ y $f \not \in O(1)$ decimos que el programa es lineal.
• Si $f \in O(n^2)$ y $f \not \in O(n)$ decimos que el programa es cuadrático.
• Si $f \in O(n^3)$ y $f \not \in O(n^2)$ decimos que el programa es cúbico.
• En general si i $f \in O(n^k)$ decimos que el programa es polinomial.
• Si $f \in O(2^n)$ o similar decimos que el programa es exponencial.

Tiempo de ejecución en el peor caso

• El TEPC de un programa es la suma de los TEPCs de sus instrucciones.
• El TEPC de una operación elemental es 1.
• El TEPC de un if then else es de $t(B) + \max\big(t(S1), t(S2)\big)$.
• El TEPC de un while es de $t(B) + \text{cant. de iteraciones} \cdot \big(t(B) + t(S)\big)$