What are common examiner traps in Asymptotic Analysis?

Assuming every pair of functions is asymptotically comparable (e.g. failing on oscillating functions like n1+sin n where lim does not exist). Confusing logb a in Master Theorem when f(n) contains polylogarithmic factors (e.g. Case 1 vs Case 2 extended). Forgetting to substitute back the original variable n after using substitution m = log n or k = loga logb n. Believing that A(n) = (W(n)) always holds, whereas only A(n) = O(W(n)) is universally true. Incorrectly assuming worst-case of n operations is n × (worst-case of single operation) instead of performing aggregate analysis. Misinterpreting (N) as mutually exclusive with O(N) or (N) when it strictly implies both. Confusing loop iteration count with the returned accumulator value when the accumulator increments by a non-constant expression like n/2 rather than 1. Assuming nested loops automatically yield (n2) or (n log n) without checking whether step reductions follow a geometric series (n + n/2 + n/4 + = 2n = (n)). Forgetting that f(n) ∈ o(g(n)) automatically implies f(n) ∈ O(g(n)), but f(n) ∈ O(g(n)) does not imply f(n) ∈ o(g(n)). Overlooking substitution requirements for non-standard recurrences before trying to blindly apply the standard Master Theorem form T(n) = aT(n/b) + f(n). Assuming a naive pairwise check ∀ i > j requires (n2) time when the relation is transitive and can be verified via adjacent pairs in (n) time.

GATE CSE Asymptotic Analysis PYQs

Medium yield24.2% of Algorithms

Across GATE CS exam papers, asymptotic complexity is evaluated through rigorous mathematical analysis and algorithmic code inspection. Questions consistently fo… Read the guide

Take topic test

Questions: 31
Asked: since 2011
Total marks: 45
Marks / paper: 1.9

31 GATE CSE Asymptotic Analysis PYQs with solutions, from Algorithms. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

GATE CSE 2026 Set 1 · Q17Consider the following recurrence relations: For all $n > 1$ , $T_1(n) = 4T_1\left(\frac{n}{2}\right) + T_2(n)$ $T_2(n) = 5T_2\left(\frac{n}{4}\right) + \Theta(\log_2 n)$ Assume that for all $n \le 1$ , $T_1(n) = 1$ and $T_2(n) = 1$ . Which one of the following options is correct?MCQ1 markMediumSolve
GATE CSE 2026 Set 2 · Q24Consider the following functions, where $n$ is a positive integer. $n^{1/3}\ ,\ \log(n)\ ,\ \log(n!)\ ,\ 2^{\log(n)}$ Which one of the following options lists the functions in increasing order of asymptotic growth rate? *Note:* Assume the base of $\log$ to be 2.MCQ1 markEasySolve
GATE CSE 2026 Set 2 · Q25Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$ ?MSQ1 markEasySolve
GATE CSE 2026 Set 2 · Q38Consider an array $A$ of integers of size $n$ . The indices of $A$ run from $1$ to $n$ . An algorithm is to be designed to check whether $A$ satisfies the condition given below. $\forall i, j \in \{1, \dots, n - 1\} \text{ such that } i > j, (A[i + 1] - A[i]) > (A[j + 1] - A[j])$ Which one of the…MCQ2 marksEasySolve
GATE CSE 2025 Set 1 · Q20Consider the following recurrence relation: $T(n) = 2T(n - 1) + n2^n \text{ for } n > 0, \quad T(0) = 1.$ Which ONE of the following options is CORRECT?MCQ1 markEasySolve
GATE CSE 2024 Set 1 · Q17Given an integer array of size $N$ , we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm isMCQ1 markEasySolve
GATE CSE 2024 Set 1 · Q42Consider the following recurrence relation: $T(n) = \begin{cases} \sqrt{n} T(\sqrt{n}) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}$ Which one of the following options is CORRECT?MCQ2 marksMediumSolve
GATE CSE 2023 · Q29Let $f$ and $g$ be functions of natural numbers given by $f(n) = n$ and $g(n) = n^2$ . Which of the following statements is/are TRUE?MSQ1 markEasySolve
GATE CSE 2023 · Q54Consider functions $\textbf{Function\_1}$ and $\textbf{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 whileFunction_2 for i = 1 to 100 * n do x = x + 1; end for…MSQ2 marksMediumSolve
GATE CSE 2022 · Q11Which one of the following statements is TRUE for all positive functions $f(n)$ ?MCQ1 markMediumSolve
GATE CSE 2021 Set 1 · Q3Consider the following three functions. $f_1 = 10^n \qquad f_2 = n^{\log n} \qquad f_3 = n^{\sqrt{n}}$ Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?MCQ1 markEasySolve
GATE CSE 2021 Set 1 · Q30Consider the following recurrence relation. $T(n) = \begin{cases} T(n/2) + T(2n/5) + 7n & \text{if } n > 0 \\ 1 & \text{if } n = 0 \end{cases}$ Which one of the following options is correct?MCQ2 marksMediumSolve
GATE CSE 2021 Set 2 · Q39For constants $a \ge 1$ and $b > 1$ , consider the following recurrence defined on the non-negative integers: $T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)$ Which one of the following options is correct about the recurrence $T(n)$ ?MCQ2 marksEasySolve
GATE CSE 2020 · Q2For parameters $a$ and $b$ , both of which are $\omega(1)$ , $T(n) = T(n^{1/a}) + 1$ , and $T(b) = 1$ . Then $T(n)$ isMCQ1 markMediumSolve
GATE CSE 2020 · Q6What is the worst case time complexity of inserting $n^2$ elements into an AVL-tree with $n$ elements initially?MCQ1 markMediumSolve
GATE CSE 2017 Set 1 · Q4Consider the following functions from positive integers to real numbers: $10,\ \sqrt{n},\ n,\ \log_2 n,\ \frac{100}{n}$ The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:MCQ1 markEasySolve
GATE CSE 2017 Set 2 · Q3Match the algorithms with their time complexities:MCQ1 markEasyDiagramSolve
GATE CSE 2017 Set 2 · Q30Consider the recurrence function $T(n) = \begin{cases} 2T(\sqrt{n}) + 1, & n > 2 \\ 2, & 0 < n \le 2 \end{cases}$ Then $T(n)$ in terms of $\Theta$ notation isMCQ2 marksMediumSolve
GATE CSE 2017 Set 2 · Q38Consider the following C function.int fun(int n) { int i, j; for(i = 1; i <= n; i++) { for(j = 1; j < n; j += i) { printf(" %d %d",i,j); } } }Time complexity of fun in terms of $\Theta$ notation isMCQ2 marksMediumSolve
GATE CSE 2016 Set 2 · Q39The given diagram shows the flowchart for a recursive function $\text{A}(n)$ . Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the worst case time complexity of this function is $O(n^\alpha)$ , then the least possible value (accurate up to two decimal positions) of $\alpha$ …NAT2 marksMediumDiagramSolve
GATE CSE 2015 Set 1 · Q2Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting $n$ ( $\ge 2$ ) numbers? In the recurrence equations given in the options below, $c$ is a constant.MCQ1 markEasySolve
GATE CSE 2015 Set 1 · Q31Consider the following C function.int fun1(int n) { int i,j,k,p,q=0; for (i=1; i<n; ++i) { p=0; for (j=n; j>1; j=j/2) ++p; for (k=1; k<p; k=k*2) ++q; } return q; }Which one of the following most closely approximates the return value of…MCQ2 marksMediumSolve
GATE CSE 2015 Set 3 · Q4Consider the equality $\sum_{i=0}^{n} i^3 = X$ and the following choices for $X$ I. $\Theta(n^4)$ II. $\Theta(n^5)$ III. $O(n^5)$ IV. $\Omega(n^3)$ The equality above remains correct if $X$ is replaced byMCQ1 markMediumSolve
GATE CSE 2015 Set 3 · Q42Let $f(n) = n$ and $g(n) = n^{(1 + \sin n)}$ , where $n$ is a positive integer. Which of the following statements is/are correct? I. $f(n) = O(g(n))$ II. $f(n) = \Omega(g(n))$ MCQ2 marksMediumSolve
GATE CSE 2014 Set 1 · Q42Consider the following pseudo code. What is the total number of multiplications to be performed?D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3MCQ2 marksMediumSolve
GATE CSE 2014 Set 2 · Q13Which one of the following correctly determines the solution of the recurrence relation with $T(1) = 1$ ? $T(n) = 2T\left(\frac{n}{2}\right) + \log n$ MCQ1 markEasySolve
GATE CSE 2013 · Q18Which of the following statements are TRUE? 1. The problem of determining whether there exists a cycle in an undirected graph is in P. 2. The problem of determining whether there exists a cycle in an undirected graph is in NP. 3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time…MCQ1 markEasySolve
GATE CSE 2013 · Q31Consider the following function:int unknown(int n) { int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); }The return value of the function isMCQ2 marksMediumSolve
GATE CSE 2013 · Q44Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter.MultiDequeue (Q) { m = k while (Q is not empty) and (m > 0) { Dequeue(Q) m = m - 1 } }What is the worst case time complexity of a sequence of $n$ queue…MCQ2 marksMediumSolve
GATE CSE 2012 · Q18Let W( $n$ ) and A( $n$ ) denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$ . Which of the following is ALWAYS TRUE?MCQ1 markEasySolve
GATE CSE 2011 · Q37Which of the given options provides the increasing order of asymptotic complexity of functions $f_1, f_2, f_3$ and $f_4$ ? $f_1(n) = 2^n$ $f_2(n) = n^{3/2}$ $f_3(n) = n \log_2 n$ $f_4(n) = n^{\log_2 n}$ MCQ2 marksMediumSolve

What GATE tests in Asymptotic Analysis

Concepts, patterns, formulas and traps distilled from past papers.

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, \Omega, \Theta, o, \omega$ ) and practical application to standard algorithmic procedures.

Core concepts

Formal definitions of asymptotic notations (O, , , o, )
Properties of asymptotic notations (transitivity, symmetry, reflexivity, polynomial scaling)
Divide-and-conquer recurrences and Master Theorem
Variable transformation / substitution techniques for recurrences
Recursion tree method and Akra-Bazzi method for non-uniform divide-and-conquer splits
Amortized aggregate analysis for sequences of operations
Logarithmic base comparisons using log f(n) transformations
Nested loop execution counting and Harmonic series approximations
Worst-case vs Average-case running time relationships (A(n) ≤ W(n))
Big-O, Little-o, Big-Omega, Little-omega, and Big-Theta formal definitions
Stirling's approximation and logarithm identities in growth ranking
Nested loop iteration counting and variable accumulation
Geometric summation in while-loop step analysis
Recurrence relation solving via variable substitution (n = 2m) and normalization factors
Master Theorem for divide-and-conquer recurrences
Equivalence reduction of array pairwise predicates to local adjacent checks

Recurring question patterns

Function Growth Rate Comparison and Sorting
CommonMCQ1 marks2022, 2021, 2017, 2015
Given a set of 3 to 5 mathematical functions involving exponents, roots, logarithms, powers, and oscillating terms, determine their increasing order of asymptotic growth rate or evaluate asymptotic relationships between them.
Recurrence Relation Solving
CommonMCQ2 marks2026, 2021, 2020, 2017
Solving divide-and-conquer recurrences with Master Theorem, variable substitution for square roots / power reductions ( $T(n) = 2T(\sqrt{n}) + 1$ , $T(n) = T(n^{1/a}) + 1$ ), non-standard branch factors ( $T(n) = T(n/2) + T(2n/5) + 7n$ ), or cascading/dependent recurrences.
Nested Loop and Code Snippet Complexity Analysis
CommonMCQ2 marks2017, 2015, 2014
Analyzing iterative C snippets or pseudocode where inner loop bounds depend on outer loop indices (e.g. step sizes $j += i$ giving harmonic sums, or exponential doubling/halving counters yielding $\log \log n$ ).
Formal Asymptotic Bounds and Complexity Relationships
OccasionalMCQ1 marks2024, 2022, 2015, 2013
Testing theoretical definitions and properties of $O, \Omega, \Theta, o$ notations, such as the relation between worst-case and average-case runtimes ( $A(n) = O(W(n))$ ), polynomial transformations ( $f(n^2) = \Theta(f(n)^2)$ ), or membership in P/NP/NP-Complete.
Data Structure and Algorithmic Worst-Case Scaling
OccasionalMCQ1.5 marks2020, 2017, 2015, 2013
Evaluating worst-case time across a sequence of operations using aggregate amortized analysis (e.g. MultiDequeue), repeated data structure operations (e.g. inserting $n^2$ elements into an AVL tree of size $n$ ), or algorithm matching.
Solving Non-Standard Recurrence Relations via Substitution
CommonMCQ2 marks2025, 2024
Recurrences featuring non-standard terms such as square roots $T(n) = \sqrt{n}T(\sqrt{n}) + n$ or exponential coefficients $T(n) = 2T(n-1) + n2^n$ that require dividing through by an integrating factor or applying variable substitution ( $n = 2^m$ ) before applying standard recurrence techniques.
Loop Step Counting and Return Value Analysis
Commonmixed2 marks2023, 2013
Analyzing nested or sequential loops where step counters or accumulator variables increase at varying rates (e.g., halving step sizes generating geometric series, or logarithmic step sizes combined with non-unit increments to variables).
Asymptotic Growth Ordering and Notation Validation
Commonmixed1 marks2026, 2023
Comparing explicit functions (e.g., $n^{1/3}, \log n, \log(n!), 2^{\log n}$ ) or testing formal definitions ( $O, o, \Omega, \Theta, \omega$ ) using limit tests between two given functions.
Multiple Recurrence Matching to Target Bound
OccasionalMSQ1 marks2026
Given several candidate recurrences (linear decrease vs divide-and-conquer), identifying which ones evaluate to a specified target complexity such as $\Theta(n)$ .
Optimal Algorithm Complexity for Property Verification
OccasionalMCQ2 marks2026
Given a formal mathematical property on an array structure (e.g., transitivity of consecutive differences), establishing the tight worst-case time complexity of the optimal algorithm to check that property.

Formulas GATE uses

Standard Master Theorem for Divide and Conquer

T(n) = aT\left(\frac{n}{b}\right) + f(n) \implies T(n) = \begin{cases} \Theta(n^{\log_b a}) & f(n) = O(n^{\log_b a - \epsilon}) \\ \Theta(n^{\log_b a} \log n) & f(n) = \Theta(n^{\log_b a}) \\ \Theta(f(n)) & f(n) = \Omega(n^{\log_b a + \epsilon}) \text{ and } af(n/b) \le cf(n) \end{cases}

Solving recurrences with balanced subproblems and polynomial overhead.

Variable Substitution for Root and Power Recurrences

n = 2^m \implies T(2^m) = S(m), \quad T(\sqrt{n}) = S(m/2)

Converting non-linear recurrences of the form $T(n) = aT(\sqrt{n}) + f(n)$ into standard divide-and-conquer forms.

Harmonic Series Loop Bound

\sum_{i=1}^{n} \frac{n}{i} = n \sum_{i=1}^{n} \frac{1}{i} = n \cdot H_n = \Theta(n \log n)

Nested loops where inner loop step size or limit depends proportionally on the outer loop index $i$ .

Akra-Bazzi Characteristic Exponent

\sum_{i=1}^{k} a_i b_i^p = 1 \implies T(n) = \Theta\left(n^p \left(1 + \int_1^n \frac{g(u)}{u^{p+1}} du\right)\right)

Recurrences with unequal subproblem sizes, such as $T(n) = T(n/2) + T(2n/5) + 7n$ .

Sum of Powers of Consecutive Integers

\sum_{i=1}^{n} i^k = \Theta(n^{k+1}), \quad \sum_{i=0}^n i^3 = \frac{n^2(n+1)^2}{4} = \Theta(n^4)

Nested loops iterating over triangular or combinatorial indices and checking asymptotic bounds.

Limit Definition of Asymptotic Notations

\lim_{n \to \infty} \frac{f(n)}{g(n)} = c \implies \begin{cases} f \in o(g) & c = 0 \\ f \in \Theta(g) & 0 < c < \infty \\ f \in \omega(g) & c = \infty \end{cases}

Used when verifying asymptotic relations ( $O, o, \Omega, \Theta, \omega$ ) between two standard functions.

Recurrence Variable Transformation (Square Root)

T(n) = \sqrt{n}T(\sqrt{n}) + n \implies \frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}} + 1 \xrightarrow{n=2^m} G(m) = G(m/2) + 1

Used to convert square root recursive arguments into standard divide-and-conquer forms.

Recurrence Integrating Factor (Exponential Term)

T(n) = 2T(n-1) + n2^n \implies \frac{T(n)}{2^n} = \frac{T(n-1)}{2^{n-1}} + n \implies S(n) = S(n-1) + n

Used to simplify linear decrease recurrences with exponential non-homogeneous terms.

Stirling's Asymptotic Approximation for Factorials

\log(n!) = \Theta(n \log n)

Used when comparing the asymptotic growth rate of factorial logarithmic functions against polynomials and logs.

Logarithmic Base Exponent Identity

b^{\log_b(n)} = n

Used when simplifying exponentiated log expressions to rank asymptotic growth.

Decreasing Halving Geometric Series

\sum_{k=0}^{\lfloor \log_2 n \rfloor} \frac{n}{2^k} = n \left( 1 + \frac{1}{2} + \frac{1}{4} + \dots \right) = \Theta(n)

Used when an outer loop halves $n$ on each pass while an inner loop runs $n$ times.

Examiner traps in Asymptotic Analysis

Assuming every pair of functions is asymptotically comparable (e.g. failing on oscillating functions like n1+sin n where lim does not exist).
Confusing logb a in Master Theorem when f(n) contains polylogarithmic factors (e.g. Case 1 vs Case 2 extended).
Forgetting to substitute back the original variable n after using substitution m = log n or k = loga logb n.
Believing that A(n) = (W(n)) always holds, whereas only A(n) = O(W(n)) is universally true.
Incorrectly assuming worst-case of n operations is n × (worst-case of single operation) instead of performing aggregate analysis.
Misinterpreting (N) as mutually exclusive with O(N) or (N) when it strictly implies both.
Confusing loop iteration count with the returned accumulator value when the accumulator increments by a non-constant expression like n/2 rather than 1.
Assuming nested loops automatically yield (n2) or (n log n) without checking whether step reductions follow a geometric series (n + n/2 + n/4 + = 2n = (n)).
Forgetting that f(n) ∈ o(g(n)) automatically implies f(n) ∈ O(g(n)), but f(n) ∈ O(g(n)) does not imply f(n) ∈ o(g(n)).
Overlooking substitution requirements for non-standard recurrences before trying to blindly apply the standard Master Theorem form T(n) = aT(n/b) + f(n).
Assuming a naive pairwise check ∀ i > j requires (n2) time when the relation is transitive and can be verified via adjacent pairs in (n) time.

How questions are asked

Function ranking / ordering lists
Recurrence relation asymptotic evaluation
Code snippet / nested loop time complexity
Matching algorithms to time complexity
True/False theoretical statements on asymptotic notations
Flowchart / recursive path maximum work tracing
Code snippet return value / step counter asymptotic evaluation
Direct asymptotic relation truth evaluation (MSQ with O, o, , )
Sorting functions in increasing/decreasing order of growth rate
Recurrence relation closed-form asymptotic classification
Multi-recurrence matching to a given complexity target (MSQ)
Optimal worst-case complexity for verifying an array invariant

Paper trends

Shift from basic Master Theorem questions to variable substitutions (e.g., $n = 2^m$ or $n = b^{a^k}$ ) and multi-term non-uniform splits requiring Akra-Bazzi or recursion tree summations.
2021, 2020, 2017, 2014
Introduction of cascading/dependent recurrences where one recurrence's asymptotic solution forms the non-recursive overhead $f(n)$ of another recurrence.
2026
Increasing emphasis on precise mathematical proofs and definitions of asymptotic notations over naive intuition (e.g., oscillating sinusoidal functions where neither $O$ nor $\Omega$ holds, and tight bound $\Theta(N)$ implying both $O(N)$ and $\Omega(N)$ ).
2024, 2022, 2015
Introduction of MSQ format to test asymptotic definitions ( $O, o, \Omega, \Theta, \omega$ ) where multiple options can be valid simultaneously.
2026, 2023
Shift from straightforward Master Theorem recurrences toward domain/range substitutions (e.g., $S(n) = T(n)/n$ with $n=2^m$ , and $S(n) = T(n)/2^n$ ).
2025, 2024
Testing algorithm design optimality from formal predicate specifications alongside traditional code snippet analysis.
2026

Difficulty notes

Easy questions (1 mark) typically involve direct Master Theorem applications, classic algorithm matching (Binary Search, Heap Sort, Matrix addition), standard function ordering with distinct polynomial degrees, or foundational definitions ( $A(n) = O(W(n))$ ). Medium/Hard questions (2 marks) require variable substitutions ( $n = 2^m$ or double logs), non-uniform recurrences (Akra-Bazzi), harmonic loop bounds ( $j += i$ ), aggregate analysis on compound data structure routines, nested logarithmic loop variables yielding $\log \log n$ , or flowchart tracing to formulate recurrences.