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 &lt; chars.length; i++) {
      result.push(prefix + chars[i]);
      f(prefix + chars[i], chars.slice(i + 1));
    }
  }
  f('', chars);
  return result;
}
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 &gt; 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)$.