retagged by
1,525 views
8 votes
8 votes

How many asterisks $(*)$ in terms of $k$ will be printed by the following C function, when called as $\text{count}(m)$ where $m = 3^k \ ?$ Justify your answer.

Assume that $4$ bytes are used to store an integer in C and $k$ is such that $3^k$ can be stored in $4$ bytes.

void count(int n){
    printf("*");
    
    if(n>1){
        count(n/3);
        count(n/3);
        count(n/3);
    }
}
retagged by

4 Answers

Best answer
12 votes
12 votes
Recurrence relation goes like this:
$$T(n)=3T\left(\frac{n}{3}\right)+1 \qquad \to (1) $$
Using substitution,
$$T(n)= 3\left(3T\left(\frac{\frac{n}{3}}{3}\right) +1\right) +1$$
$$ \implies T(n)=3^2T\left(\frac{n}{3^2}\right)+3+1 \qquad \to(2) $$
Use substitution again,
$$T(n)= 3^2\left(3{T\left(\frac{n}{3^3}\right)} +1 \right) +3 +1 $$
$$\implies T(n)= 3^3T\left(\frac{n}{3^3}\right) + 3^2 + 3 + 1 $$
$$\implies T(n)= 3^3T\left(\frac{n}{3^3}\right) + 3^2 + 3^1 +3^0\qquad \to (3)$$
Continuing like this up to $'k'$ times we get,
$$T(n)= 3^kT\left(\frac{n}{3^k}\right)+3^{k-1} + 3^{k-2}+\ldots+ 3^1 + 3^0\qquad \to (4)$$
put $n=3^k$ which is what question says i.e., $n =3^k$  (I am considering '$n$' in place of '$m$' as name doesn't matter here)
$$T(n)= 3^k + 3^{k-1} + 3^{k-2} + 3^{k-3}+\ldots +3^1 + 3^0$$                                                      
Solving above G.P. series with $a = 1, r=3$ we get
$$T(n)= \frac{{3^{k+1} -1}}{{3-1}}= \frac{3^{k+1}-1}{2}$$
selected by
13 votes
13 votes
I tried it for $3^5$ ,

in every call it print "$*$" one time

and each function call $3$ functions for $n/3$ recursively till get $1$ at each node . it becomes a ternary tree

call for $3^5$ -----------------------$1 = 3^0$

call for $3^4$ -----------------------$3 = 3^1$

call for $3^3$ -----------------------$9 = 3^2$

call for $3^2$ ---------------------$27 =3^3$

call for $3^1$ ---------------------$81 = 3^4$

call for $3^0$ -------------------$243 = 3^5$

so one "$*$" print at each function call

no of "$*$" printed $= 3^0 +3^1 +3^2 +......3^k $ [ that makes GP series ]

 $= 1 * (1 - 3^{k+1})/(1-3)$

 $= (3^{k+1} -1 )/2 $

[ Note : I am not sure about it , feel free for edit ]
edited by
3 votes
3 votes

T(3k) = 3T(3k-1)+1, This is the recurrence relation of the above program. +1 is number of times *is printed, so during 1st call 1 * will be printed.

T(3k) = 3T(3k-1) + 1

         = 32(T(3k-2) + 3 + 1

          = 33(T(3k-3) + 9 + 3 + 1.....

          continue upto k-1

1 + 3 + 32 + ..... 3k-1= 1(1- 3k-1)/1-3

Related questions

3 votes
3 votes
2 answers
2
2 votes
2 votes
3 answers
3
jjayantamahata asked Mar 15, 2018
666 views
Let $X_1,X_2,X_3,X_4$ be i.i.d. random variables each assuming the value $1$ and $-1$ with probability $\dfrac{1}{2}$ each. Then, the probability that the matrix $\begin{...