GATE 2023 CS – Question 54
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 forLet $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?
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)$.
- (A) $f_1\in\Theta(f_2)$: true.
- (B) $f_1\in o(f_2)$ (grows strictly slower): false, they grow at the same rate.
- (C) $f_1\in\omega(f_2)$ (strictly faster): false.
- (D) $f_1\in O(n)$: true.
Answer: A, D.
More Asymptotic Analysis and Time/Space Complexity questions
- GATE 2022 CS Q11
- GATE 2022 CS Q51
- GATE 2021 CS (CS1) Q13
- GATE 2021 CS (CS1) Q40
- GATE 2020 CS Q12
- GATE 2019 CS Q47
All Asymptotic Analysis and Time/Space Complexity questions →