Algoritmos | Análisis de Algoritmos | Pregunta 19 – Part 1

Considere las siguientes dos funciones. ¿Cuáles son las complejidades temporales de las funciones?

int fun1(int n)
{
    if (n <= 1) return n;
    return 2*fun1(n-1);
}

int fun2(int n)
{
    if (n <= 1) return n;
    return fun2(n-1) + fun2(n-1);
}

(A) O(2^n) para fun1() y fun2()
(B) O(n) para fun1() y O(2^n) para fun2()
(C) O(2^n) para fun1() y O(n) para fun2()
(D) O(n) tanto para fun1() como para fun2()

Respuesta: (B)
Explicación: La complejidad temporal de fun1() se puede escribir como
T(n) = T(n-1) + C que es O(n)

La complejidad temporal de fun2() se puede escribir como
T(n) = 2T(n-1) + C, que es O(2^n)

Cuestionario de esta pregunta