time and space complexity

Question

I have a doubt related with time and space complexity in following 2 case

Blockquote

Case I:

Recurion: Factorial calculation.

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

here how come time complexity become 2*n and space complexity proportional to n.

and

Case II:

Iterative:-

int fact(int n)
{
    int i, result = 1;
    if(n==0)
    result = 1;
    else
         {
           for(1=1;i<=n;i++)
              result*=i;
         }
     return (result);
}

Time complexity proportional to n and space complexity is constant. This always remain confusing to me.

Answer 1

If my reasoning is faulty, somebody please correct me :)

For the space complexity, here's my explanation:

For the recursive solution, there will be n recursive calls, so there will be n stacks used; one for each call. Hence the O(n) space. This is not the case for the iterative solution - there's just one stack and you're not even using an array, there is only one variable. So the space complexity is O(1).

For the time complexity of the iterative solution, you have n multiplications in the for loop, so a loose bound will be O(n). Every other operation can be assumed to be unit time or constant time, with no bearing on the overall efficiency of the algorithm. For the recursive solution, I am not so sure. If there are two recursive calls at each step, you can think of the entire call stack as a balanced binary tree, and the total number of nodes will be 2*n - 1, but in this case I am not so sure.