GATE CSE 2023 Q54: Comparing a halving loop with a 100n loop

Algorithms
2 marks
MSQ
No negative marking

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?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, D (official GATE 2023 final answer key)

Concept used: A geometric series $n + n/2 + n/4 + \cdots$ is at most $2n$ .

First step: Write $f_1(n) \approx n + \frac n2 + \frac n4 + \cdots$ and $f_2(n) = 100n$ , then compare.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key

PracticePractise Algorithms questions →Full paperAll GATE CSE 2023 questions →

GATE CSE 2023 Q54: Comparing a halving loop with a 100n loop

Question

Full step-by-step solution

More Algorithms PYQs