1
$\begingroup$

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;
}
Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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]? $\endgroup$ – plop Dec 19 '20 at 13:41
  • $\begingroup$ @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 $\endgroup$ – Ashera Dec 19 '20 at 14:10
  • $\begingroup$ 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. $\endgroup$ – plop Dec 19 '20 at 14:18
  • $\begingroup$ @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. $\endgroup$ – Ashera Dec 20 '20 at 6:37
1
$\begingroup$

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)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.