Complexity of a function

Question

What is the time and space complexity of:

int superFactorial4(int n, int m)
{
    if(n <= 1)
    {
        if(m <= 1)
            return 1;
        else 
            n = m -= 1;
    }

    return n*superFactorial4(n-1, m);
}

It runs recursively by decreasing the value of n by 1 until it equals 1 and then it will either decrease the value of m by 1 or return 1 in case m equals 1.

I think the complexity depends on both n and m so maybe it's O(n*m).

Answer 1

The time complexity is O(n+m^2), space complexity the same.

Reasoning: with a fixed value of m, the function makes n recursive calls to itself, each does constant work, so the complexity of calls with fixed m is n. Now, when n reaches zero, it becomes m-1 and m becomes m-1 too. So the next fixed-m-phase will take m-1, the next m-2 and so on. So you get a sum (m-1)+(m-2)+...+1 which is O(m^2).

The space complexity is equal, because for each recursive call, the recursion takes constant space and you never return from the recursion except at the end, and there is no tail recursion.

Answer 2

Actually, it looks to be closer to O(N+m^2) to me. n is only used for the first "cycle".

Also, in any language that doesn't do tail call optimization the space complexity is likely to be "fails". In languages that support the optimization, the space complexity is more like O(1).