Register

Please explain this Q

• recategorized by
509 views
0 votes
0 votes

Consider the following C program

int f1(int n)
{
  if(n == 0 || n == 1)
    return n;
  else
    return (2*f1(n-1) + 3*f1(n-2));
}

Consider the program given in above question, f1(8) and f2(8) return the values

A

1661 and 1640

B

59 and 59

C

1640 and 1640

D

1640 and 1661
• recategorized by
User Avatar

2 Answers

0 votes
0 votes
According to me,the question should me f1(8) and f1(8)

f1(0)=0   f1(1)=1  Base Condition

f1(2)=2*f(1) + 3*f1(0), i e 2*1 + 3*0 =2 f1(2)=2

f1(3)=2*f1(2)+3*f1(1) =2*2+3*1=7 f1(3)=7

f1(4)=2*f1(3)+3*f1(2)=2*7 + 3*2 f1(4)=20

similarly f1(5)=61

f1(6)=182

f1(7)=547

f1(8)=1640

Option C should correct.
Check  if am correct
User Avatar
0 votes
0 votes

Firstly edit f2 to f1

Use bottom up evaluation it will be very easy to find values i.e, first evaluate f1(2) then f1(3) etc........

when n>1 then use return statement

Base conditions are:-

if(n==1) return n i.e, 1 and if(n==0) return n i.e, 0 

Base conditions are used to stop the recursive program otherwise it will fall in infinite loop....

Now how to evaluate f1(2):-

Here n=2 which is greater than 1 so we can use return statement i.e 2*f1(n-1)+3*f1(n-2) = 2*f1(1)+3*f1(0) = 2*1+3*0 = 2

therefore f1(2)=2

Similarly f1(3) = 2*f1(2)+3*f1(1) = 2*2+3*1 = 4+3 = 7 [since f1(2)=2 we computed]

f1(4) = 2*f1(3)+3*f1(2) = 2*7+3*2=14+6=20 [since f1(3)=7 and f1(2)=2]

Computing values this way we get:-

f1(5)=61 

f1(6)=182

f1(7)=547

and f1(8)= 1640

Therefore answer will be 1640 and 1640

Time complexity equation:-

T(n)=2*T(n-1)+3*T(n-2)+1 [1 is added for if condition statement]

solving equation by back substitution we get

T(n)=O(2n)

Corrections are welcome.....

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
Çșȇ ʛấẗẻ asked Aug 27, 2016
320 views
Algo# Can anybody can explain in detail ???
Consider the following function int madeeasy(int n) { if (n<=0) return; else { print(n); madeeasy(n-2); print(n); madeeasy(n-1); } } What is the some of all values printed by madeeasy(5)?
Consider the following functionint madeeasy(int n) { if (n<=0) return; else { print(n); madeeasy(n-2); print(n); madeeasy(n-1); } }What is the some of all values printed ...
User Avatar
1 votes
1 votes
1 answer
2
kaveeshnyk asked May 7, 2019
1,092 views
Can anyone please explain this question step by step
#include<stdio.h> int main(){ int (*a)[5]; int arr[5][5]={ {10,65,300,400,500}, {100,20,3000,40,5000} }; a = arr; ++a ; char *ptr = (char*)*a; ++a ; printf("%d %d %d",**a,*arr[1],*ptr); return 0; }
#include<stdio.h int main(){ int (*a)[5]; int arr[5][5]={ {10,65,300,400,500}, {100,20,3000,40,5000} }; a = arr; ++a ; char *ptr = (char*)*a...
User Avatar
7 votes
7 votes
3 answers
3
Parshu gate asked Nov 20, 2017
783 views
Output of program. Please explain how this works
What is the output of the following program? #include<stdio.h> int main() { int array[]={10, 20, 30, 40}; printf(“%d”, -2[array]); return 0; } $-60$ $-30$ $60$ Garbage value
What is the output of the following program?#include<stdio.h int main() { int array[]={10, 20, 30, 40}; printf(“%d”, -2[array]); return 0; }$-60$$-30$$60$Garbage valu...
User Avatar
0 votes
0 votes
1 answer
4
kallu singh asked Dec 14, 2017
384 views
How to Solve This Q
User Avatar
Link Copied!