Algorithms · Asymptotic Analysis
Official IIT answer key · IIT Kanpur · Audited Aug 2026
GATE CSE 2023 Q54 · MSQ · 2 marks
Function_1
while n > 1 do
for i = 1 to n do
x = x + 1;
end for
n = ⌊n/2⌋;
end whileFunction_2
for i = 1 to 100 * n do
x = x + 1;
end for
Let f1(n) and f2(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?Key concept
No account needed
Sit 5 related Asymptotic AnalysisPYQs as a guest. We'll score the set and show which traps cost marks — sign in only if you want to save the run.
Topic notes
Across GATE CS exam papers, asymptotic complexity is evaluated through rigorous mathematical analysis and algorithmic code inspection. Questions consistently focus on solving recurrence relations (using the Master Theorem, Akra-Bazzi, recursion trees, and variable substitution), ranking growth rates of non-trivial functions (including log-log, oscillating, and super-polynomial forms), and calculating the exact operation counts of nested loops and multi-step data structure operations. The evaluation spans both conceptual formal definitions (O, , , o, ) and practical application to standard algorithmic procedures.
Full Asymptotic Analysis guide →Consider functions Function\1 and Function\2 expressed in pseudocode as follows: Function1 while n > 1 do for i = 1 to n do x = x + 1; end for n = ⌊n/2⌋; end while Function2 for i = 1 to 100 * n do x = x + 1; end for Let f1(n) and f2(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?
Topic-wise GATE CS PYQs with verified steps
Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.