Reference no: EM132270053
Below, is the answer to an algorithm question I answered.
Below my answer is my Professor's comment on the answer I gave.
I need someone to rework the recurrence equation.
This program returns the factorial of a given number 'n'.
n(n-1) * (n-2) .....
int fact (int n)
{
if (n==1)
{
return 1;
}
else
}
Return n * fact(n-1);
}
}//end program
The recurrence equation is below
n > 0 = Precondition
T(1) = 1
T(n) = T(n-1) * n
The amount of operations that are counted is the base case in addition to the recursive calls.
The base case stops the recursive calls at n = 1.
This decrements n until the base case.
The time complexity is 0(n) for n calls.
Professor's Comment
The recurrence equation being asked for is the one that represents the amount of work performed, not the one that defines the value of the factorial sequence.
Hence, I just need the recurrence equation reworked to satisfy his comment.
Below is the question I answered.
If I get a new copy paste answer and not a rework of the recurrence equation, you will get a down vote.
Provide an example of a recursive function in which the amount of work on each activation is constant. Provide the recurrence equation and the initial condition that counts the number of operations executed. Specify which operations you are counting and why they are the critical ones to count to assess its execution time. Draw the recursion tree for that function and determine the Big-Θ by determining a formula that counts the number of nodes in the tree as a function of n.