Una medida teórica de la ejecución de un algoritmo, generalmente el tiempo o memoria necesaria, dado el problema tamaño n, que suele ser el número de elementos. Informalmente, diciendo una ecuación f (n) = ω (g(n)) significa g (n) se convierte en insignificante en comparación con f (n) como n va hasta el infinito. Definición formal: f (n) = ω (g(n)) significa que existe una constante k, para cualquier constante positiva c, tal que cg(n) ≤ 0 < f (n) para todos n ≥ k el valor de k no debe depender de n, pero puede depender de c.