// n is a non-negative integer function f(n) if n == 0 || n == 1 return 1; else
ID: 3879149 • Letter: #
Question
// n is a non-negative integer
function f(n)
if n == 0 || n == 1
return 1;
else
return n*f(n-1);
Respond to the following:
What does the f function do? Please provide a detailed response.
In terms of n, how many computational steps are performed by the f function? Justify your response. Note: One computational step is considered one operation: one assignment, one comparison, et cetera. For example, the execution of 3*3 may be considered one computational step: one multiplication operation.
What is the Big-O (worst-case) time complexity of the f function in terms of n? Justify your response.
Define a recurrence relation an, which is the number of multiplications executed on the last line of the function f, "return n*f(n-1);", for any given input n. Hint: To get started, first determine a1, a2, a3 …. From this sequence, identify the recurrence relation and remember to note the initial conditions.
Explanation / Answer
The f function will return the factorial for a number. in the above case you are finding the factorial in recursive way.
for the above case worst and best case time complexity is O(n) only. Why because whatever the number you will give it will take those many recursions.
for example we take n as 3.
first it will check if condition it does not met the codition. it will go to return statement
3 * f(2) --> 2 * f(1) --> 1 = 3*2*1 = 6
that's how this factorial program works.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.