Complejidad temporal del algoritmo recursivo con dos llamadas recursivas

Estoy tratando de analizar la complejidad del tiempo de un algoritmo recursivo que resuelve el problema Generar todas las secuencias de bits dentro de la distancia t de Hamming . El algoritmo es este:

// str is the bitstring, i the current length, and changesLeft the // desired Hamming distance (see linked question for more) void magic(char* str, int i, int changesLeft) { if (changesLeft == 0) { // assume that this is constant printf("%s\n", str); return; } if (i < 0) return; // flip current bit str[i] = str[i] == '0' ? '1' : '0'; magic(str, i-1, changesLeft-1); // or don't flip it (flip it again to undo) str[i] = str[i] == '0' ? '1' : '0'; magic(str, i-1, changesLeft); } 

¿Cuál es la complejidad temporal de este algoritmo?


Me siento bastante oxidado cuando se trata de esto y aquí está mi bash, que siento que no está ni cerca de la verdad:

 t(0) = 1 t(n) = 2t(n - 1) + c t(n) = t(n - 1) + c = t(n - 2) + c + c = ... = (n - 1) * c + 1 ~= O(n) 

donde n es la longitud de la cadena de bits.

Preguntas relacionadas: 1 , 2 .

Es exponencial :

 t(0) = 1 t(n) = 2 t(n - 1) + c t(n) = 2 (2 t(n - 2) + c) + c = 4 t (n - 2) + 3 c = 2 (2 (2 t(n - 3) + c) + c) + c = 8 t (n - 3) + 7 c = ... = 2^it(ni) + (2^i - 1) c [at any step i] = ... = 2^nt(0) + (2^n - 1) c = 2^n + (2^n - 1) c ~= O(2^n) 

O, usando WolframAlpha: https://www.wolftwiglpha.com/input/?i=t(0)%3D1 ,+t(n)%3D2+t(n-1)+%2B+c

La razón por la que es exponencial es que sus llamadas recursivas están reduciendo el tamaño del problema en 1, pero está haciendo dos llamadas recursivas. Tus llamadas recursivas están formando un árbol binario.