Programming in C

Question

How many asterisks (*) in terms of k will be printed by the following C
function, when called as count(m) where m = 3k? Justify your answer.
Assume that 4 bytes are used to store an integer in C and k is such that
3k can be stored in 4 bytes.
void count(int n)
{
printf("*");
if(n>1)
{
count(n/3);
count(n/3);
count(n/3);
}
}

Answer 1

Lets take simple case when n=9, you will have a recursion tree as follows-

              9

    3        3          3

1 1 1   1 1 1    1 1 1

This is nothing but perfect 3-ary tree.

At each node, you have a printf statement. So we need to count no of nodes in such tree.

No. of levels(x) for given n in such tree will be ceil(log₃n).

Total no of nodes in perfect 3-ary tree = (3^x-1)/2 = (3^{ceil(log₃n)}-1)/2

In this question n=3k, So total no of printf statements(total no of nodes in recursion tree)=(3^{ceil(log₃3k)}-1)/2

Comments

hint-:

$T\left ( n \right )=3T\left ( \frac{n}{3} \right )+1$

---

Excellent :)