I'm struggling to understand how to effectively determine the time complexity of recursive code. While I can see how we can find the time complexity for code that has two recursive calls (e. g. recursive fib) as O(2^n), I struggle to dertime it when there are n recursions. Here is an example:
Quick note: I tried to come up with an easy example. I admit that there's very likely a formula to calculate size of the "powerset/superset" and gives us the work needed. My question is more generic and should relate to all times when one resursion can produce n additional recursions.
var subsets = function(nums) {
const result = [];
function traverse(arr, start) {
result.push(arr)
for (let i = start; i < nums.length; i++) {
traverse([...arr, nums[i]], i + 1);
}
}
traverse([], 0)
return result;
};