IAE Academy

GATE 2023 CS Q.54: solution and answer

GATE 2023 · CSQ.54 · 2 marks · MSQ

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 and denote the number of times the statement "" is executed in Function_1 and Function_2, respectively.

Which of the following statements is/are TRUE?

  1. (A)

  2. (B)

  3. (C)

  4. (D)

See the question in the paper
GATE 2023 CS question 54Tap to open full size

Answer and solution

ANSWER

GATE CS 2023 Q.54 (MSQ, 2 marks): The correct answers are (A) and (D).

Official answer: A, DSource: Official answer key, GATE 2023 CS (IIT Kanpur)

  1. Function_1: the outer while loop runs while n>1, and each pass halves n via n=⌊n/2⌋. The inner for loop runs from i=1 to the current value of n, executing x=x+1 that many times per pass.

  2. So f1(n) = n + ⌊n/2⌋ + ⌊n/4⌋ + ... (continuing until n drops to 1), which — dropping floors, which don't affect asymptotic order — is a geometric series with ratio 1/2: n·(1 + 1/2 + 1/4 + ...) which sums to at most 2n.

  3. Hence f1(n) = Θ(n): it is bounded above by 2n and below by its leading term n (both linear in n), giving tight linear growth.

  4. Function_2: the single for loop runs i=1 to 100·n, executing x=x+1 exactly 100n times, so f2(n) = 100n = Θ(n).

  5. Option A — f1(n) ∈ Θ(f2(n)): since f1(n) ≈ 2n and f2(n) = 100n, the ratio f1(n)/f2(n) → 2/100, a positive constant, so both the upper- and lower-bound conditions for Θ hold. TRUE.

  6. Option B — f1(n) ∈ o(f2(n)): little-o demands the ratio f1(n)/f2(n) → 0, but the ratio tends to the constant 1/50, not 0. FALSE.

  7. Option C — f1(n) ∈ ω(f2(n)): little-omega demands the ratio → ∞, but again the ratio is a fixed constant. FALSE.

  8. Option D — f1(n) ∈ O(n): since f1(n) ≤ 2n for all sufficiently large n (constant c=2 suffices), this upper bound holds. TRUE.

  9. Correct (TRUE) options: A and D.

KEY IDEA

Trace each loop's exact iteration count rather than guessing from loop nesting depth: Function_1's outer while halves n each pass while the inner for runs the current n, giving a geometric series that sums to — the same order as Function_2's single pass of iterations. Two functions of the same order satisfy (tight bound) and (upper bound) with each other, but never or (which require the ratio to actually vanish or blow up).

WATCH OUT FOR

Assuming Function_1's nested while+for structure must be or just because it looks like two loops, without summing the geometric series (which totals , not ); a second common slip is treating "same order" as automatically implying little- or little-, when those need the ratio of the two functions to tend to or respectively, not merely to be unequal.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 14 Complexity questions, with notes

More Complexity questions