What are common examiner traps in Algorithms?

Assuming every pair of functions is asymptotically comparable (e.g. failing on oscillating functions like n1+ n where does not exist). Confusing b 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 = n or k = a b 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 n) without checking whether step reductions follow a geometric series (n + n/2 + n/4 + = 2n = (n)).

Algorithms

16 topics · 121 Qs · 7.8 marks/paper · since 2011

Start mock (30 Qs)

Across GATE CS exam papers, asymptotic complexity is evaluated through rigorous mathematical analysis and algorithmic code inspection. Across GATE CS exams, Searching, Sorting, and… Guide

By year

Jump to the first question from that paper.

Subject guide

What does GATE test in Algorithms?

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

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+ n where does not exist).
Confusing b 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 = n or k = a b 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 n) without checking whether step reductions follow a geometric series (n + n/2 + n/4 + = 2n = (n)).

How questions show up

Function Growth Rate Comparison and Sorting
common · MCQ · 1 marks · 2022, 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
common · MCQ · 2 marks · 2026, 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
common · MCQ · 2 marks · 2017, 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
occasional · MCQ · 1 marks · 2024, 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
occasional · MCQ · 1.5 marks · 2020, 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
common · MCQ · 2 marks · 2025, 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.

Algorithms

16 topics · 121 Qs · 7.8 marks/paper · since 2011

Start mock (30 Qs)

Across GATE CS exam papers, asymptotic complexity is evaluated through rigorous mathematical analysis and algorithmic code inspection. Across GATE CS exams, Searching, Sorting, and… Guide

By year

Jump to the first question from that paper.

Subject guide

What does GATE test in Algorithms?

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

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+ n where does not exist).
Confusing b 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 = n or k = a b 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 n) without checking whether step reductions follow a geometric series (n + n/2 + n/4 + = 2n = (n)).

How questions show up

Function Growth Rate Comparison and Sorting
common · MCQ · 1 marks · 2022, 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
common · MCQ · 2 marks · 2026, 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
common · MCQ · 2 marks · 2017, 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
occasional · MCQ · 1 marks · 2024, 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
occasional · MCQ · 1.5 marks · 2020, 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
common · MCQ · 2 marks · 2025, 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.

Algorithms

Topics

By year

Core concepts

High-yield formulas

Examiner traps in Algorithms

How questions show up

Algorithms

Topics

By year

Core concepts

High-yield formulas

Examiner traps in Algorithms

How questions show up