Algoritmos | Análisis de Algoritmos | Pregunta 2

¿Cuál es la complejidad temporal de fun()?

int fun(int n)
{
  int count = 0;
  for (int i = 0; i < n; i++)
     for (int j = i; j > 0; j--)
        count = count + 1;
  return count;
} 

(A) Theta (n)
(B) Theta (n^2)
(C) Theta (n*Logn)
(D) Theta (nLognLogn)

Respuesta: (B)
Explicación: La complejidad del tiempo se puede calcular contando el número de veces la expresión “cuenta = cuenta + 1;” es ejecutado. La expresión se ejecuta 0 + 1 + 2 + 3 + 4 + …. + (n-1) veces.

Complejidad del tiempo = Theta(0 + 1 + 2 + 3 + .. + n-1) = Theta (n*(n-1)/2) = Theta(n 2 ) Cuestionario ^de esta
pregunta