Consider this recursive function foo(N): int foo(int N){ if (N <= 1) return 5; r
ID: 3861265 • Letter: C
Question
Consider this recursive function foo(N): int foo(int N){ if (N <= 1) return 5; return foo(N-2) * foo(N-2); } Use the function definition as is. There is no error. a) (3 points) Write the recurrence formula for this function. b) (3 points) Solve the recurrence formula you gave above to compute the bigO complexity of this function. c) (6 points) Draw the tree that shows the function calls performed in order to compute foo(7) (the root will be foo(7) and it will have a child for each recursive call.) 3 d) (6 points) Use the tree to compute the number of function calls as a function of N (not the specific number of recursive function calls for foo(7), but a formula that would give the number of calls for any N. SHOW YOUR WORK. (Continue on the next page if needed) e) (6 points) Is it possible to re-implement this function so that it has running time O(N)? If not, why not? If yes, write this O(N) implementation of foo in C.
Explanation / Answer
Each decision to foo returns either one or 2 lines. If n <= one, we tend to solely execute one line (the if/return). if n = 3, execute two for foo(2), and one every for foo(1) and foo(0): four
It's just like the rabbits! apart from the 2 lines in every decision, the time for n is that the total of the days for 2 smaller algorithmic calls.
time(n) = two + time(n-1) + time(n-2)
In general, any algorithmic formula like this one offers United States of America a repetition relation: the time for any routine is that the time inside the routine itself, and the time for the algorithmic calls. this offers associate exceedingly|in a terribly} very straightforward mechanical method an equation just like the one on top of, that we are able to then solve to search out a formula for the time. during this case, the repetition relation is incrediblyalmost like the definition of the numbers.
With some work, we are able to solve the equation, a minimum of in terms of Foo(n): we predict of the formula as forming a tree. we tend to draw one node, the foundation of the tree, for the primary decision then any time the routine calls itself, we tend to draw another child within the tree.
Foo(5)
/
Foo(4) Foo(3)
/ /
Foo(3) Foo(2) Foo(2) Foo(1)
/
Foo(2) Foo(1)
The four internal nodes of this tree for foo(5) take 2 lines every, whereas the 5 leaves take one line, therefore the total variety of lines dead altogether the algorithmic calls is thirteen.
Note that, after we do that for any decision to foo, the variety Foo(i) at every internal node is simply the quantity of leaves below that node, therefore the total variety of leaves within the tree is simply Foo(n). keep in mind that leaves count jointly line of code, internal nodes a pair of. To count internal nodes, use basic truth concerning binary trees (trees within which every node has a pair of children): the quantity of internal nodes perpetually equals the quantity of leaves minus one. (You will prove this by induction: it's true if there is one leaf and no internals, and it stays true if you add a pair of youngsters to a leaf.)
So there square measure Foo(n) lines dead at the leaves, and 2Foo(n)-2 at the interior nodes, for a complete of 3Foo(n)-2. Let's assay this on a straightforward example: time(5) = 3Foo(5) - a pair of = 3(5)-2 = one
Yes it possible to re-implement this function so that it has running time O(N)
int main()
{
int n, f = 0, s = 1, n, c;
printf("Enter total number of terms ");
scanf("%d",&n);
printf("First %d terms of Fibonacci series are :- ",n);
for ( c = 0 ; c < n ; c++ )
{
if ( c <= 1 )
n= 5;
else
{
n = f + s;
f= s;
s = n;
}
printf("%d ",n);
}
return 0;
}