PUERTA | PUERTA CS 2013 | Pregunta 31

Considere la siguiente función:

int unknown(int n) {
    int i, j, k = 0;
    for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;
 }

(A)

(B)

(C)

(D)

(A) A
(B) B
(C) C
(D) D

Respuesta: (B)
Explicación: Aquí tenemos que decir el valor de k devuelto, no la complejidad del tiempo. 
 

for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;

El ciclo externo se ejecuta n/2 veces. 
El ciclo interno se ejecuta logn veces. (2^k = n => k = logn). 
Ahora, mirando el valor de k en el ciclo interno, n se agrega a k, tiempos de registro a medida que el ciclo interno se ejecuta tiempos de registro. 
Por lo tanto, la complejidad del tiempo total es interna multiplicada por la complejidad del ciclo externo, que (n para externo y nlogn para interno) n*logn. 

Por lo tanto, el valor de k después de ejecutar el ciclo interno una vez es n^2logn.
Ver http://geeksquiz.com/algorithms-analysis-of-algorithms-question-5/
Esta solución es aportada por Parul Sharma.

Cuestionario de esta pregunta