Por ejemplo en la búsqueda binaria, el tamaño del problema que resolver es dividido en mitades en cada iteración, y por lo tanto se necesitarán lg "n" iteraciones para resolver un problema de tamaño n.