Algoritmos | Análisis de Algoritmos | Pregunta 18

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;
 }

¿Cuál es el valor de retorno de la función? (PUERTA CS 2013)

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

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

Respuesta: (B)
Explicación: En la siguiente explicación, ‘^’ se usa para representar el exponente:
El bucle externo se ejecuta n/2 o Theta(n) veces .
El bucle interno se ejecuta (Iniciar sesión) veces (tenga en cuenta que j se multiplica por 2 en cada iteración).
Así que la declaración «k = k + n/2;» ejecuta Theta(nLogn) veces.
La declaración aumenta el valor de k en n/2.
Entonces el valor de k se convierte en n/2*Theta(nLogn) que es Theta((n^2) * Logn).

Cuestionario de esta pregunta