Algoritmos | Análisis de Algoritmos | Pregunta 14

En la siguiente función C, sea n >= m.

int gcd(n,m)
{
  if (n%m ==0) return m;  
  n = n%m;
  return gcd(m, n);
}

¿Cuántas llamadas recursivas realiza esta función?
(A) (logn)
(B) (n)
(C) (loglogn)
(D) (sqrt(n))
(A) A
(B) B
(C) C
(D) D

Respuesta: (A)
Explicación: El código anterior es la implementación del  algoritmo euclidiano  para encontrar el máximo común divisor (GCD).
Consulte  http://mathworld.wolfram.com/EuclideanAlgorithm.html  para conocer la complejidad del tiempo.
Cuestionario de esta pregunta