The GATE Grind

GATE 2023 CS – Question 54

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple select

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

Function 1
while n > 1 do
  for i = 1 to n do
    x = x + 1;
  end for
  n = n/2;
end while

Function 2
for i = 1 to 100 * n do
  x = x + 1;
end for

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?

  1. $f_1(n) \in \Theta(f_2(n))$
  2. $f_1(n) \in o(f_2(n))$
  3. $f_1(n) \in \omega(f_2(n))$
  4. $f_1(n) \in O(n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $f_1(n) \in \Theta(f_2(n))$; (D) $f_1(n) \in O(n)$

Explanation

f1(n) = n + n/2 + n/4 + … ≈ 2n = Θ(n) and f2(n) = 100n = Θ(n). So f1 ∈ Θ(f2) and f1 ∈ O(n), while o and ω do not hold.