Question

What is the time complexity ?

int fact(int n)

{ if( n==1)

{return 1;}

n=n*fact(n-1);

return n;

}

Answer 1

The given function is

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

This is a program to calculate factorial.

Time complexity when parameter passed is 1

when 1 is passed it returns 1, and it includes only one comparision i..e if(n == 1) , nothing else is executed

So

T(1) = 1

Calculating T(n)

When any number is passed below opeations are done

time for one comparison(if (n==1)), time for one multiplication(n * fact(n-1)), time for one subtraction(n - 1)

and time for fact(n-1)

so

T(n) = T(n-1) + 3

= T(n-2) + 3 + 3 = T(n - 2) + 2*3

= T(n - 3) + 3 + 3 + 3 = T(n - 3) + 3*3

= T(n - k) + k * 3 = T(n-k) + 3k

T(1) = 1

if we put

n - k = 1

k = n + 1

T(n) = T(n - n + 1) + 3(n + 1)

= T(1) + 3n + 3

= 1 + 3n + 3

= 3n + 4

= O(n)

So O(n) is answer