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.)