GATE CS 2018 Q45 — Asymptotic Worst Case Time and Space Complexity

To find the number of times the print statement is executed, let us analyze the recursion behavior of Count(x, y) starting with Count(1024, 1024).

For any fixed value of $y \neq 1$:

• The function checks if $x \neq 1$. If true, it prints "*" and recursively calls Count(x/2, y).
• Starting with $x = 1024$, the sequence of $x$ values that trigger a print is:
  $1024 \to 512 \to 256 \to 128 \to 64 \to 32 \to 16 \to 8 \to 4 \to 2$
  This sequence has exactly $\log_2(1024) = 10$ steps. Thus, 10 asterisks are printed.
• When $x$ reaches $1$, the else block is executed: $y$ is decremented by $1$, and the function is called again as Count(1024, y - 1).

This process repeats for each value of $y$ starting from $1024$ down to $2$. When $y = 1$, the outer condition y != 1 becomes false, and the recursion terminates.

The number of active values of $y$ is:

$$1024, 1023, \dots, 2 \implies 1023 \text{ values}$$

Since exactly 10 prints occur for each of these 1023 values of $y$, the total number of times the print statement is executed is:

$$1023 \times 10 = 10230$$