# Time complexity of a recursive function which generates all combinations of an array

The following function getCombinations, is a recursive function that can be used to generate all combinations of an array. How exactly can we find the time complexity of this function? I would appreciate the workings or simply an idea about how to approach this. Thanks in advance

function getCombinations(chars) {
var result = [];
var f = function(prefix, chars) {
for (var i = 0; i < chars.length; i++) {
result.push(prefix + chars[i]);
f(prefix + chars[i], chars.slice(i + 1));
}
}
f('', chars);
return result;
}

• Call $T(p,n)$ the number of operations that $f$ would do for an input in which the length of prefix is $p$ and the length of chars is $n$. The definition of $f$ gives you are recurrence relation and initial condition for $T$. Solve this recurrence. The the number of steps that getCombinations does is $T(0,n)$. A number of questions will need to be answered before: How many operations, in that particular implementation of that language, does it take to do result.push(prefix + chars[i]);? How many does it tak to do chars.slice(i + 1)? How many for prefix + chars[i]? – plop Dec 19 '20 at 13:41
• @plop I am not referring to a specific language here. This is a pseudocode for the task of combination generation. However, to answer your query, we could assume O(1) for addition, slicing, and push operations. Or if you have a suggestion please share your opinion too – Ashera Dec 19 '20 at 14:10
• Pseudocode is language too and the assumptions about addition, slicing and push are required to answer the problem. There is also another thing that I forgot that needs to be specified. What is the output of those operations. push and + I can guess, from their behavior in other computer languages, but for chars.slice(i + 1) I have more than one guess. – plop Dec 19 '20 at 14:18
• @plop the expected behavior is as follows: list => [1, 2, 3] combinations => [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}] push would simply append that entry to the list. + is used to add integers as well as to concatenate elements in the original list. chars.slice(i+1) is used to extract a slice of elements from the original list. – Ashera Dec 20 '20 at 6:37

Denote by $$T(n)$$ the running time of your function on an input of length $$n$$, assuming that all operations are $$O(1)$$. Then $$T(0) = O(1)$$, and for $$n > 0$$, $$T(n) = O(n) + \sum_{m=0}^{n-1} T(m).$$ Let us replace $$O(n)$$ with $$Cn$$. Then $$T(n) - T(n-1) = Cn + \sum_{m=0}^{n-1} T(m) - C(n-1) - \sum_{m=0}^{n-2} T(m) = C + T(n-1),$$ and so $$T(n) = 2T(n-1) + C$$, implying that $$T(n) + C = 2(T(n-1) + C)$$. Therefore $$T(n) = 2^n(T(0) + C) - C = O(2^n)$$.