PUERTA | GATE-CS-2017 (Conjunto 2) | Pregunta 49

Considere la siguiente función C.

int fun(int n)
{
    int i, j;
    for (i = 1; i <= n ; i++)
    {
        for (j = 1;  j < n; j += i)
        {
            printf("%d %d", i, j);
        }
    }
}

La complejidad temporal de la diversión en términos de la notación θ es:
(A) θ(n √n)
(B) θ(n ² )
(C) θ(n log n)
(D) θ(n ² log n)

Respuesta: (C)
Explicación: Veamos cuántas veces la sentencia más interna “printf(“%d %d”, i, j);” es ejecutado.

Para i = 1, la sentencia se ejecuta n veces.
La i-ésima iteración, la sentencia se ejecuta Θ(n/i) veces.

Sumando todas las iteraciones para i = 1 an, obtenemos
Así T(n) = Θ(n(1 + 1/2 +1/3 + ….)) = Θ(n log n).

Tenga en cuenta que el valor de 1/1 + 1/2 + 1/3 + …. 1/n es aproximadamente igual que Log n para valores grandes de n.
Cuestionario de esta pregunta