retagged by
12,996 views
35 votes
35 votes

Consider the following program written in pseudo-code. Assume that $x$ and $y$ are integers.

Count (x, y) {
    if (y !=1 ) {
        if (x !=1) {
            print("*");
            Count (x/2, y);
        }
        else {
            y=y-1;
            Count (1024, y);
        }
    }
}

The number of times that the $print$ statement is executed by the call $Count(1024, 1024)$ is _____

retagged by

7 Answers

5 votes
5 votes

Look at the function. It's recursive. We write it mathematically as stated below.

$\mathrm{Count}(x,y)= \left\{\begin{matrix} \emptyset & y= 1\\ \mathrm{Count}(\lfloor \frac{x}{2}\rfloor,y) & x\ne 1, y\ne 1 \\ \mathrm{Count}(1024,y-1) & x=1, y\ne 1 \end{matrix}\right.$

It means the first parameter $x$ is being halved by every call until $x=1$. In fact, the first parameter $x$ is decreased geometrically (logarithmically based 2) like $(1024,512,256,...,1)$. On the other hand, the second parameter $y$ is linearly decreasing by 1 until $y=1$ like $(1024,1023,1022,...,1)$.

So roughly the number of times $\mathrm{Count}(x,y)$ being called $=O(\log_{2}(x)+y)$. More accurately it is $\log_{2}x +\log_{2}(1024) \times (y-2)$

 

$\therefore$ The number of times $\mathrm{Count}(1024,1024)$ being called is $$\begin{align}\log_{2}(1024) +\log_{2}(1024) \times (1024-2)&={\log_{2}(1024)}\times(1024-1)\\&=10\times 1023=10230 \end{align}$$

 

So the correct answer is $10230$.
 

edited by
4 votes
4 votes

$C(1024,1024)$$\rightarrow*$

             $\downarrow$

$C(512,1024)\rightarrow*$

             $\downarrow$

$C(256,1024)\rightarrow*$

             $\downarrow$

$C(128,1024)\rightarrow*$

             $\downarrow$

$C(64,1024)\rightarrow*$

             $\downarrow$

$C(32,1024)\rightarrow*$

             $\downarrow$

$C(16,1024)\rightarrow*$

             $\downarrow$

$C(8,1024)\rightarrow*$

             $\downarrow$

$C(4,1024)\rightarrow*$

             $\downarrow$

$C(2,1024)\rightarrow*$

             $\downarrow$

$C(1,1024)$

             $\downarrow$

$C(1024,1023)$


Similary for $C(1024,1023)=10\ stars$ & so on until $C(1024,2)=10\ stars$

$For\ C(1024,1)$ Program terminates

$\therefore$ It runs 1023 times & each time 10 stars generated leading to $1023\times 10=10230\ stars$

0 votes
0 votes

I have declared a new global variable “count” for better understanding

Count() is called recursively for every (y=1023) & for every y, count() is called (x=10) times=1023x10=10230 printf will execute

 

Answer:

Related questions

23 votes
23 votes
5 answers
1
38 votes
38 votes
5 answers
2
gatecse asked Feb 14, 2018
21,937 views
Consider the weights and values of items listed below. Note that there is only one unit of each item.$$\begin{array}{|c|c|c|}\hline \textbf{Item number} & \textbf{Weigh...
35 votes
35 votes
9 answers
3
gatecse asked Feb 14, 2018
17,335 views
Consider the following undirected graph $G$:Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $...