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;
}
prefix
is $p$ and the length ofchars
is $n$. The definition of $f$ gives you are recurrence relation and initial condition for $T$. Solve this recurrence. The the number of steps thatgetCombinations
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 doresult.push(prefix + chars[i]);
? How many does it tak to dochars.slice(i + 1)
? How many forprefix + chars[i]
? $\endgroup$ – plop Dec 19 '20 at 13:41push
and+
I can guess, from their behavior in other computer languages, but forchars.slice(i + 1)
I have more than one guess. $\endgroup$ – plop Dec 19 '20 at 14:18list => [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. $\endgroup$ – Ashera Dec 20 '20 at 6:37