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

**Function 1.** The `for` loop runs $n$ times, then $n$ halves, and so on while $n>1$:
$$f_1(n)=n+\frac n2+\frac n4+\dots\approx2n.$$
**Function 2.** The `for` loop runs $100n$ times: $f_2(n)=100n$.

Both are linear: $f_1(n)=\Theta(n)$ and $f_2(n)=\Theta(n)$.

Answer: A, D.

More Asymptotic Analysis and Time/Space Complexity questions

All Asymptotic Analysis and Time/Space Complexity questions →