Pregunta 2.d y 2.e · Prácticas de programación UOC 2021

Se facilita la siguiente función recursiva desarrollada en lenguaje C:

#define MAX 42

int guess(int v[MAX], int p, int d)

{

int result;

assert(0 <= p && p < MAX && d > 0);

if (p == 0) {

if (v[0] % d == 0) result = 1; // (1)

else result = 0; // (2)

} else { // (3)

result = guess(v, p-1, d); // (4)

if (v[p] % d == 0) result++; // (5)

} // (6)

return result; // (7)

}

d.

Calcula y argumenta la complejidad asintótica temporal del algoritmo original en su formato recursivo.

e.

Frente a una propuesta alternativa para el método guess con un orden de complejidad casi-lineal ($O(n \log n)$), razona en 4 o 5 líneas si convendría adoptar dicha propuesta.