PUERTA | Sudo GATE 2020 Mock III (24 de enero de 2019) | Pregunta 49

¿Cuál es la complejidad temporal de la siguiente función fun()? Suponga que log(x) devuelve el valor de registro en base 2.

void fun() 
{ 
   int i, j; 
   for (i=1; i<=n; i++) 
      for (j=1; j<=log(i); j++) 
         printf("GeeksforGeeks"); 
} 

(A) Θ(n)
(B) Θ(n log log n)
(C) Θ(n log n)
(D) Θ(n^2)

Respuesta: (C)
Explicación: Opción (C) Θ(n log n) es correcta.

Consulte – Una prueba de preguntas sobre la complejidad del tiempo
de esta pregunta