Una pregunta interesante sobre la complejidad del tiempo.

¿Cuál es la complejidad temporal de la siguiente función fun()?

int fun(int n)
{    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j += i)
        {
            // Some O(1) task
        }
    }    
}

Para i = 1, el ciclo interno se ejecuta n veces.
Para i = 2, el ciclo interno se ejecuta aproximadamente n/2 veces.
Para i = 3, el ciclo interno se ejecuta aproximadamente n/3 veces.
Para i = 4, el ciclo interno se ejecuta aproximadamente n/4 veces.
……………………………………………………….
……………………………………………………….
Para i = n, el ciclo interno se ejecuta aproximadamente n/n veces.

Entonces, la complejidad temporal total del algoritmo anterior es (n + n/2 + n/3 + … + n/n)

Que se convierte en n * (1/1 + 1/2 + 1/3 + … + 1/n)

Lo importante de la serie (1/1 + 1/2 + 1/3 + … + 1/n) es que es igual a Θ(Logn) (Vea esto como referencia). Entonces, la complejidad temporal del código anterior es Θ(nLogn).

Como nota al margen, la suma de series armónicas infinitas es contraria a la intuición ya que la serie diverge. El valor de es ∞. Esto es diferente a las series geométricas, ya que las series geométricas con una relación inferior a 1 convergen.

Referencia:
http://en.wikipedia.org/wiki/Harmonic_series_%28mathematics%29#Rate_of_divergence
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap03.htm

Este artículo es una contribución de Rahul . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.