Runtime complexity of recursion inside loop

Question

I try to determine the runtime complexity of the following code. I came up with T(n) = n * T(n-1) + n where T(0) = 1 but not sure if it's correct and how to solve it.

private void myFunction(int[] nums, int startIndex, int target) {
    if (target == 0) {
        // do something
    }
    if (target <= 0 || start > nums.length) {
        return;
    }

    for (int i = startIndex; i < nums.length; i++) {
        myFunction(nums, i+1, target-nums[i]);
    }
}

myFunction(nums, 0, target);

In the function why do you require so many parameters? please put some comments to the code — User27854, Aug 24 '17 at 05:58

score 0 · Answer 1 · answered Aug 24 '17 at 07:01

I guess the recurrence relation for the function is T(n) = n * T(n-1) + O(1), where T(0) = 1

Reduction:

T(n) 
= n * T(n-1) + O(1)
= n * (n-1) * T(n-2) + 1 + 1
= n * (n-1) * (n-2) * T(n-3) + 1 + 1 + 1
...
= n * (n-1) * (n-2) * (n-3) ... T(0) + n * 1 (n times)
= n! + n

Hence, the overall complexity for the function is O(n!) which is greater O(2ⁿ). More details.

Hope it helps!

Runtime complexity of recursion inside loop

1 Answers1