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

and

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

respectively

Dark Mode

srestha
asked
in Programming
May 12, 2019

864 views
2 votes

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?$

2 votes

Best answer

If we give n=0 then printf will execute only 1 time (else part will not execute) so

option ashould 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,*f**o**r **n*>0;1 *f**o**r** 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.)

0