Question

ALGORITHM ANALYSIS AND DESIGN

Analyze the given questions and answer accordingly

1.       Given the algorithm to calculate the factorial of ‘n’. Mathematically analyze the given recursive algorithm to find out the time complexity of the algorithm.   

Algorithm F(n)

If n = 0 return 1

Else

Return f(n-1) * n

Answer 1

We want to find the time complexity of the given algorithm.

First case:So from the algorithm, we can see that if the number is 0, it will return 0.Which means the algorithm have one comparison when the value of n is 0.

We can write this as,

for f(0), T(0)=1

Second case:If the number is n, we can observe that it include one comparison to check whether n is 0 or not, then it have one multiplication and one subtraction. And also it require time to perform f(n-1).

We can write this as,

for f(n), T(n)=T(n-1)+3

From the above details we can find the time complexity as,

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

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

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

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

Now substitute (2), (3) and (4) in (1),

T(n)=T(n-2)+6

=T(n-3)+9

=T(n-4)+12

=....

=......

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

We know that T(0)=1

We want to find the value of k where n-k=0, which means n=k.

So we write the equation (5) as,

T(n)=T(0)+3n because n=k

T(n) =1+3n

From above we can write that the time complexity of the given algorithm is O(n)