GATE CS 2003 Q88 — Asymptotic Worst Case Time and Space Complexity

To find the set of numbers printed by the program, let us analyze the conditions under which a number $j$ is printed.

1. Initialization: The array elements $A[j]$ are initialized to $0$ for all $j \in [3, n]$.
2. Update Rule: The nested loops update $A[j]$ as: $$A[j] = A[j] \lor (j \% k)$$ for all $k \in [2, \text{TwoLog\_n}]$ such that $k < j$. This means $A[j]$ becomes $1$ if there is at least one $k$ in the range $[2, \min(j-1, \text{TwoLog\_n})]$ that does not divide $j$.
3. Condition for Printing: For $j$ to be printed, we must have $A[j] = 0$ at the end, which requires $j$ to be divisible by all integers $k$ in the range $[2, \min(j-1, \text{TwoLog\_n})]$.

Let us analyze the two possible cases for any $j \in [3, n]$:

• Case 1: $j - 1 \le \text{TwoLog\_n}$
  Here, $j$ must be divisible by $j-1$. For any $j \ge 3$, $j$ can never be divisible by $j-1$ (since $j-1 > j/2$). Thus, $A[j]$ will always become $1$.
• Case 2: $j - 1 > \text{TwoLog\_n}$
  Here, $j$ must be divisible by all integers from $2$ up to $\text{TwoLog\_n} = 2\lceil \log_2 n \rceil$. This means $j$ must be a multiple of the Least Common Multiple: $$L = \text{LCM}(2, 3, \dots, 2\lceil \log_2 n \rceil)$$ Since $L$ grows exponentially, $L > n$ for all $n \ge 3$. Because $j \le n$, no such multiple $j$ can exist in the range $[3, n]$.

Since $A[j]$ becomes $1$ for every $j \in [3, n]$, the condition !A[j] is never met, and no numbers are printed. The printed set is empty, $\{\}$.