function solution(a, k) {
    let result = [];
    result = count(start = 0, result, a, curr = [], 2, 0);
    return result.length
}

function count(start, result, a, curr, currLen) {
    if (curr.length === currLen) {
        if (result.includes(curr)) return;
        if (curr[0] < curr[1]) result.push([...curr]);
        return;
    }

    for (let i = start; i < a.length; i  ) {
        curr.push(i);
        count(i   1, result, a, curr, currLen, times  = 1);
        curr.pop();
    }

    return result;
}

const a1 = [1, 2, 3, 4, 5];

Would the time complexity be O(a.length)?

Is the space complexity simply O(2 * result.length) = O(result.length)?

If you could please give an explanation of how to approach this problem, it would be much appreciated. Thank you.

CodePudding user response：

No, it wouldn't.

Even assuming that the 1st part of count code is O(1) (which depends on implementation of push, but it probably is O(curr.length), the second part, the recursive one, cost is apparently O(2**a.length).

To evaluate the complexity of a recursive function, you often end up defining a recursive series mimicking the recursion of the function itself. Here

Cost(n) = Cost of count(start=a.length-n)
Cost(n) = 1   Cost(n-1) Cost(n-2) ... Cost(1) Cost(0)

Which means that Cost(n) is O(2**n).

(built it from the bottom: Cost(0)=1 ; Cost(1)=1 1 ; Cost(2) = Cost(1) Cost(0) 1=2 1 1=4 ; Cost(3)=Cost(2) Cost(1) Cost(0) 1 = 4 2 1 1=8 ; ...)

CodePudding user response：

Apparently there are a few things that are never used, or not needed:

• k is never used.
• times is an undefined variable
• count is called with a 6^th argument that is not going anywhere.
• The values in array a are never used, only its length, so we could just omit a and only work with the length value
• result.includes(curr) always returns false, but does represent work, so it cannot be discarded for determining time complexity.
• curr[0] < curr[1] is always true (because the recursive call is made with i 1 for start)

Time complexity

We may assume that push and pop have amortised O(1) time complexity. Also [...curr] has O(1) time complexity because the length of curr is curLen, which is constant (2).

The time to perform the recursive call is also constant per time that curr is pushed to the result, as the recursion depth is curLen.

If we ignore the includes call, the time complexity is driven by the number of times the base case is executed, i.e. how many subarrays are pushed to the result array. This number is the number of ways to choose curLen items of a.length items. In other words, with curLen equal to 2, it is