What are common examiner traps in Algorithms?

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)).

GATE CSE Algorithms (ALGO) PYQs

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

Start mock · 30 Qs

Topics: 16
Questions: 121
Marks / paper: 7.8
Asked: since 2011

These are the 121 GATE CSE Algorithms PYQs (since 2011), grouped topic-wise with solutions. See all GATE CSE PYQs or GATE CSE question papers by year.

Topics

Open a topic to browse its questions, or practice it as a timed test.

By year

Jump to the first question from each year’s paper.

What GATE tests in Algorithms

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. Across GATE CS exams, Searching, Sorting, and Hashing are tested with a strong emphasis on exact comparison/swap counts, worst/best-case edge cases (especially for Quicksort and simultaneous min-max finding), trace-based simulation (such as step-by-step hashing probes and merge passes), and asymptotic tradeoffs for specialized or composite data inputs. GATE tests Graph Traversals (BFS and DFS) through deep theoretical properties rather than simple code tracing.

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

How questions show up

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.

High-yield formulas

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.

Examiner traps in Algorithms

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)).

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