CODEWITHSUNDEEP
complexity-theory
yyy
yyy

Reputation: 912

Complexity of a function

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

Upvotes: 0

Views: 5320

Answers (3)

kamal
kamal

Reputation: 1

The time complexity of a Factorial function using recursion pseudo code:

int fact(n)
{ 
   if(n==0)
   { 
      return 1;
   }
   else if(n==1)
   {
        return 1;
   }
   else if
   {
      return n*f(n-1);
   }
}

time complexity;     
let T(n) be the number of steps taken to compute fact(n).


we know in each step F(n)= n*F(n-1)+C

F(n-1)= (n-1)*F(n-2)+c

substitute this in F(n), we get

F(n)= n*(n-1)*F(n-2)+(n+1)c

using big o notation now we can say that

F(n)>= n*F(n-1)
F(n)>= n*(n-1)*F(n-2)
.
.
.
.
.
F(n)>=n!F(n-k)

T(n)>=n!T(n-k)

n-k=1;
k=n-1;

T(n)>=n!T(n-(n-1))
T(n)>=n!T(1)
since T(1)=1
T(n)>=1*n!

now it is in the form of

 F(n)>=c(g(n))

so we can say that time complexity of factorial using recursion is 

T(n)= O(n!)

Upvotes: -1

jpalecek
jpalecek

Reputation: 47770

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.

Upvotes: 3

Darron
Darron

Reputation: 21620

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

Upvotes: 3

Related Questions