search
Log In
2 votes
250 views

Consider the following function $foo()$

void foo(int n){
  if(n<=0) printf("Bye");
  else{
      printf("Hi");
      foo(n-3);
      printf("Hi");
      foo(n-1);
  }
}

Let $P(n)$ represent recurrence relation, indicating number of time print statement executed. What will best recurrence for $P(n)?$

$A)P(n)=P(n-1)+P(n-3)+2,$ for $n>0; $ $1$ for $n=0$

$A)P(n)=P(n-1)+P(n-3)+2,$ for $n>0; $ $2$ for $n=0$

$A)P(n)=P(n-1)+P(n-3)+2,$ for $n>0; $ $0$ for $n=0$

$A)P(n)=P(n-1)+P(n-3)+1,$ for $n>0; $ $2$ for $n=0$


The options are confusing to me. Can someone explain the options well. Moreover , what will be constant added  $1$ or $2?$

in Programming 250 views

2 Answers

2 votes
 
Best answer

 If we give n=0 then printf will execute only 1 time (else part will not execute) so option a should be the answer by eliminating the answer.

$\rightarrow$ The constants 1 are 2 are used since the extra printf will be there if the loop does not go in the recursive conditions.

$\rightarrow$ For eg n=1.

printf("hi"); //extra print.

foo(n-3) //foo(-2)= print("Bye");  p(n-3)

printf("hi"); //extra print

foo(n-1) //foo(0)=print("bye"); p(n-1)

$\rightarrow$ so the 2 constant used is for the extra printf which i have shown in the above code.

$A)P(n)=P(n−1)+P(n−3)+2, for n>0; 1 for n=0$ is the correct answer

---------------------------------------------------------------------------------------------------------------------------------------------------------------

Why 2 and not 1 ?

$\rightarrow$ Its simple, suppose the code is

    void foo(int n){
      if(n<=0) printf("Bye");
      else{
          printf("Hi");
          
          printf("Hi");
          
      }
    }

$\rightarrow$ Now  the recurrence relation is

$\rightarrow$ P(n)= 2, for n>0; 1 for n=0

$\rightarrow$ if n=0 we are executing print statement once as we are not going in the else part.

$\rightarrow$ when n>0 we are going to the else part in which we are using 2 print statements.

$\rightarrow$ so P(n)=2 for n>0.

$\rightarrow$ Now, in the actual code we are just adding two recursive parts in the else section of the above code.

$\rightarrow$ so the recursion becomes

P(n)=P(n−1)+P(n−3)+2,for n>0;1 for n=0

    void foo(int n){
      if(n<=0) printf("Bye"); //p(n) =1 if n=0.
      else{                   // else
          printf("Hi");       // 1
          foo(n-3);           // p(n-3)
          printf("Hi");       // 1
          foo(n-1);           // p(n-1)
      }                      // i.e. p(n)= 1+p(n-3)+1+p(n-1) = P(n−1)+P(n−3)+2
    }

NOTE :- we are not doing O(1) + O(1) = O(1) since we have to count the print statements (not to calculate the time complexity.)


selected by
0
I havenot got it, why $2$ and not $1?$
0

Please check my answer @srestha

0

and what is meaning of 

1 for n=0??

and

2 for n=0 ??

0

for 1 time print statement will be executed if n=0

and

for 2 time print statement will be executed if n=0

respectively

0
ok, thanks :)
0
First will be correct as evident for n = 0  only 1 print is there
0 votes
Option A is correct as for n=0;the time complexity will be O(1) because the if statement will be executed and function will terminate after printing "Bye"

Related questions

4 votes
3 answers
1
330 views
#include<stdio.h> #include<iostream> int bar(int m, int n){ if(m==0)return n; if(n==0)return m; return bar(n%m,m); } int foo(int m,int n){ return(m*n/bar(m,n)); } int main(){ int x=foo(1000,1500); printf("%d",x); return 0; } Output of the program is ___________
asked May 20, 2019 in Programming srestha 330 views
2 votes
1 answer
2
343 views
Consider the following $C$ implementation which when given $3$ numbers a,b,c as input, find the maximum of $3$ numbers $a,b,c.$ int kickstart(int a,int b,int c) { if(B1) return a; if(a>=b) return B2; return kickstart(c,a,b); } How the boxes filled up correctly? $I)B1:a\geq b$ ... $IV)B1:a\geq b$ && $a\geq c, B2:kickstart\left ( b,c,a \right );$ Is it $I) and II)$ or $I) and IV)$
asked May 19, 2019 in Programming srestha 343 views
1 vote
0 answers
3
222 views
Consider the following C code: int getNextGap(int gap){ gap=(gap*10)/13; if(gap<1)return 1; return gap; } void mystery(int a[ ],int n){ int gap=n; bool red=true; while(gap!=1||red==true){ gap=getNextGap(gap); red=false; for(int i=0;i<(n-gap ... n is number of array elements, then what output will print at last? I mostly stuck how bool function working here. Plz help me out, how program executing:(
asked May 10, 2019 in Programming srestha 222 views
1 vote
0 answers
4
230 views
Consider the following function int fun(int a[ ],int l, int target){ int i=0,j=0,sum=0,count=0; while(j<l){ if(sum<target){ sum=sum+a[j]; j++; } else if(sum>target){ sum=sum-a[i]; i++; } else{ count++; sum=sum-a[i]; i++; } } if(sum==target) ... be return value of function call $fun\left ( a,16,8 \right )=$_______________ Given ans $6,$ but I got $4.$ Which one correct?? Any shortcut to evaluate??
asked May 8, 2019 in Programming srestha 230 views
...