ISRO | CSRO ISRO 2020 | Pregunta 21

¿Cuál es la complejidad del siguiente código?

sum = 0;
  for (i = 1; i <= n; i*= 2)
    for(j = 1; j <= n; j++)
      sum++; 

¿Cuál de las siguientes no es una string válida?
(A) Ο(n ² )
(B) Ο(n log n)
(C) Ο(n)
(D) Ο(n log n log n)

Respuesta: (C)
Explicación: Según el análisis del algoritmo anterior:

Inner loop will run unto n time, in maximum
Outer loop will run upto logn time, in maximum 

Entonces, la complejidad del tiempo total será,

= O(n) * O(log n)
= O(n logn) 

Entonces, Ο(n log n log n) y Ο(n ² ) también son correctos.
Pero no puede ser menor que O(n logn), por lo que O(n) no es correcto.

Cuestionario de esta pregunta