286 views

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);
}
}
edited | 286 views

I tried it for 35 ,

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 35 -----------------------1 = 30

call for 34 -----------------------3 = 31

call for 33  ---------------------9 = 32

call for 32  --------------------27 =33

call for 31 ---------------------81 = 34

call for 30 --------------------243 = 35

so one "*" print at each function call

no of "*" printed = 30 +31 +32 +......3k  [ that makes GP series ]

= 1 * (1 - 3k+1)/(1-3)

= (3k+1 -1 )/2

[ Note : I am not sure about it , feel free for edit ]

answered by Veteran (54.9k points) 96 248 476
selected

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

answered by Junior (741 points) 6 8 28

+1 vote