Tengo la siguiente función recursiva de arriba hacia abajo que calcula todas las diferentes formas en que podemos sumar números a partir de numbers de manera que sean iguales a targetSum . Ahora estoy tratando de determinar exactamente la complejidad temporal de este problema.

 const allWays = (targetSum, numbers) => { const fn = (remainder, startIndex) => { if (remainder === 0) return [[]]; const result = []; for (let i = startIndex; i < numbers.length; i += 1) { const num = numbers[i]; if (remainder - num < 0) continue; const remainderWays = fn(remainder - num, i); const targetWays = remainderWays.map((way) => [num, ...way]); result.push(...targetWays); } return result; }; return fn(targetSum, 0); };

Si hacemos que m sea el tamaño de targetSum y que n sea la longitud de los numbers , entonces el árbol de recurrencia debería tener una altura de m y un factor de ramificación de n , lo que le da una complejidad de tiempo de O(n^m) .

Si bien entiendo que este factor exponencial dominará todas las demás complejidades de tiempo, aún me gustaría saber qué agregan .map y dos operadores de propagación al tiempo de ejecución.

Parece que no puedo entender cuál es la complejidad temporal de este

 const targetWays = remainderWays.map((way) => [num, ...way]); result.push(...targetWays);

debiera ser.

¡Cualquier ayuda es apreciada! Gracias.