GATE CS 2023 Q.54: Asymptotic Analysis and Time/Space Complexity

Consider functions Function 1 and Function 2 expressed in pseudocode as follows:

Function 1                              Function 2
  while n > 1 do                          for i = 1 to 100 * n do
     for i = 1 to n do                       x = x + 1;
        x = x + 1;                        end for
     end for
     n = floor(n/2);
  end while

Let $f_1(n)$ and $f_2(n)$ denote the number of times the statement "x = x + 1" is executed in Function 1 and Function 2, respectively.

Which of the following statements is/are TRUE?

$f_1(n) \in \Theta(f_2(n))$

$f_1(n) \in o(f_2(n))$

$f_1(n) \in \omega(f_2(n))$

$f_1(n) \in O(f_2(n))$

Official answer and solution

Official answer: A and D
From: Official GATE 2023 answer key

Solution

Sum loop iterations for both functions and compare their asymptotic growth rates.

Function 1:
In each iteration of the while loop, the inner loop executes $n$ times, and then $n$ is halved ( $n \leftarrow \lfloor n/2 \rfloor$ ). The total executions of x = x + 1 is:
$f_1(n) = n + \lfloor n/2 \rfloor + \lfloor n/4 \rfloor + \dots + 1$
This is a geometric series bounded by $n \le f_1(n) < 2n$ . Therefore, $f_1(n) = \Theta(n)$ .
Function 2:
The loop executes for $i = 1$ to $100n$ . Hence:
$f_2(n) = 100n = \Theta(n)$
Since both functions grow linearly with $n$ ( $f_1(n) = \Theta(n)$ and $f_2(n) = \Theta(n)$ ):
- $f_1(n) \in \Theta(f_2(n))$ is TRUE (Statement A).
- $f_1(n) \in O(f_2(n))$ is TRUE (Statement D).
- Statements B ( $o$ ) and C ( $\omega$ ) are strictly false since the ratio limits to a non-zero constant ( $1/100 \le \lim f_1/f_2 \le 2/100$ ).

Final answer

Options (A, D)

Common trap

Assuming the while loop halving $n$ introduces a logarithmic term $n \log n$ , forgetting that the work halves in each step ( $n + n/2 + n/4 + \dots = 2n$ ).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 54 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source