Algoritmos | Análisis de Algoritmos | Pregunta 9

En una competición se observan cuatro funciones diferentes. Todas las funciones usan un solo bucle for y dentro del bucle for, se ejecuta el mismo conjunto de declaraciones. Considere lo siguiente para bucles:

A) for(i = 0; i < n; i++)
  
B) for(i = 0; i < n; i += 2)
  
C) for(i = 1; i < n; i *= 2)
  
D) for(i = n; i > -1; i /= 2)

Si n es el tamaño de la entrada (positivo), ¿qué función es más eficiente (si la tarea a realizar no es un problema)?
(A) A
(B) B
(C) C
(D) D

Respuesta: (C)
Explicación: La complejidad temporal del primer ciclo for es O(n).
La complejidad temporal del segundo ciclo for es O(n/2), equivalente a O(n) en análisis asintótico.
La complejidad de tiempo del tercer ciclo for es O(logn).
El cuarto bucle for no termina.
Cuestionario de esta pregunta