in Programming edited by
8,236 views
25 votes

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)$?
in Programming edited by
8.2k views

2 Answers

34 votes
 
Best answer

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$

edited by

8 Comments

can you plz explain more clearly ... as i am not getting the meaning of the code line ...??
0
How did u get the recurrence relation ? I am confused .It should be T(n) = 2* T(n+1) +1. Plz help.
0
we are decreasing length of input by 1 so that's why n-1 in recurrence relation.
5
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.
0
its not possible one other way of checking is that solve ur recurrence relation it is giving time complexity in negative which is contradiction
0

@royal shubham

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

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

1
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.
0
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.
0
4 votes
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

3 Comments

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

  

5
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?
0

 Supreet Kaur 1  

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

5

Related questions