8,236 views

Consider the following C program:

void abc(char*s)
{
if(s[0]=='\0')return;
abc(s+1);
abc(s+1);
printf("%c",s[0]);
}

main()
{
abc("123");
}
1. What will be the output of the program?
2. If $abc(s)$ is called with a null-terminated string $s$ of length $n$ characters (not counting the null ('\0') character), how many characters will be printed by $abc(s)$?

Answer (A) $:332 \ 332 \ 1$
Answer (B) $:2^n-1$

Q. (A) $O/p$ :

$3 3 2 3 3 2 1$

(B) : $T(n) = 2T(n-1) +1 ; n>0$

$\qquad = 0 ; n=0$ [Since for length zero string no character will be printed]

After solving it by substitution,

$T(n) = 2T(n-1) +1$

$\qquad = 2(2T(n-2) + 1 ) +1$

$\qquad = 2^2T(n-2) + 2 +1$

$\qquad = 2^2(2T(n-3) +1 ) + 2 + 1$

$\qquad = 2^3T(n-3) + 2^2 + 2 + 1$

Finally, it will expand like

$T(n)= 2^nT(n-n) + 2^{n-1} + 2^{n-2} + \ldots + 2^2 + 2 + 1$

$\qquad = 2^nT(0) + 2^{n-1} + 2^{n-2} + \ldots+ 2^2 + 2 + 1$

$\qquad = \frac{1.(2^n -1)}{(2 - 1)}$

$\qquad = 2^n -1$

by

can you plz explain more clearly ... as i am not getting the meaning of the code line ...??
How did u get the recurrence relation ? I am confused .It should be T(n) = 2* T(n+1) +1. Plz help.
we are decreasing length of input by 1 so that's why n-1 in recurrence relation.
how it can possible that we have problm of size n and after diving it  into subprobem it size gets incresed . its not possible , but if u r willing to increase the size of problem in each call then problem will never end.
its not possible one other way of checking is that solve ur recurrence relation it is giving time complexity in negative which is contradiction

@royal shubham

https://gateoverflow.in/754/gate2001-13?show=145156#c145156

Refer this comment... Your doubts will get clarified..

if i do something like T(n) = 2 * T(n-1) +1

= 2  x  (2  x  T(n-2)  + 1 )  +1

= 2^2 x T(n-2)  +  3

=  2^2 x (2*T(n-3) +1 )  + 2 + 1

= 2^3 x T(n-3) + 7

= [(2^n) x T(n-n)] + ((2^n - 1))

= [(2^n) x T(0) ] + ((2^n - 1))

= (2^n)  + ((2^n - 1))

=(2^(n+1)) - 1

What's wrong in this! Both solutions seems correct but gives different answer.
but the number of terms are $n+1; (2^n + 2^{n-1}+ …. +2^0)$. So the equation should be

$\frac{1.(2^{n+1} -1)}{(2 - 1)}$

Please let me know if I am wrong.
ans for B is: 2^n -1

for length 2 -> 3 characters

for length 3-> 7 characters

for length 4-> 15 characters

hence for n-> 2^n - 1 characters
by

a) 3323321

b) we can also get the answer of b by solving recurrence relation

T(n) = 2 * T(n-1) +1 ; n>0

=  0 ; n=0 [Since for length zero string no character will be printed]

After solving it by substitution,

T(n) = 2 * T(n-1) +1

= 2  x  (2  x  T(n-2)  + 1 )  +1

= 2x T(n-2)  +  2 +1

=  22 x (2*T(n-3) +1 )  + 2 + 1

= 2x T(n-3) + 22  + 2 + 1

Finally it will expand like

= 2x T(n-n) + 2n-1 + 2n-2 + - - - -  - - - + 2+ 2 + 1

= 2x T(0) + 2n-1 + 2n-2 + - - - - - - - - - - + 2+ 2 + 1

= 1x (2-1) / (2 - 1 )

= 2-1

But how do we come to this recurrence  relation first....i mean it works for all questions like this....do we have to learn this...please reply?

lets assume to solve length n input it takes T(n) times

now in ques they have two abc(s+1) and one printf

abc(s+1) reduces the length of input by 1 so now it have length (n-1)

now to solve length (n-1) input it takes T(n-1) times and printf take 1 unit of time

hence reccurence relation is :

T(n)=2.T(n-1)+1