What are common examiner traps in Asymptotic Analysis?

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

Asymptotic Analysis

31 Qs · since 2011 · 45 marks · 1.9 marks/paperMedium yield

Take topic test

Across GATE CS exam papers, asymptotic complexity is evaluated through rigorous mathematical analysis and algorithmic code inspection. Questions consistently focus on solving recur… Guide

Type

GATE CSE 2026 Set 1Q17MCQ1 markMediumConsider 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?
GATE CSE 2026 Set 2Q24MCQ1 markEasyConsider 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.
GATE CSE 2026 Set 2Q25MSQ1 markEasyWhich of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$ ?
GATE CSE 2026 Set 2Q38MCQ2 marksEasyConsider 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…
GATE CSE 2025 Set 1Q20MCQ1 markEasyConsider 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?
GATE CSE 2024 Set 1Q17MCQ1 markEasyGiven 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 is
GATE CSE 2024 Set 1Q42MCQ2 marksMediumConsider 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?
GATE CSE 2023Q29MSQ1 markEasyLet $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?
GATE CSE 2023Q54MSQ2 marksMediumConsider 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…
GATE CSE 2022Q11MCQ1 markMediumWhich one of the following statements is TRUE for all positive functions $f(n)$ ?
GATE CSE 2021 Set 1Q3MCQ1 markEasyConsider 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?
GATE CSE 2021 Set 1Q30MCQ2 marksMediumConsider 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?
GATE CSE 2021 Set 2Q39MCQ2 marksEasyFor 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)$ ?
GATE CSE 2020Q2MCQ1 markMediumFor parameters $a$ and $b$ , both of which are $\omega(1)$ , $T(n) = T(n^{1/a}) + 1$ , and $T(b) = 1$ . Then $T(n)$ is
GATE CSE 2020Q6MCQ1 markMediumWhat is the worst case time complexity of inserting $n^2$ elements into an AVL-tree with $n$ elements initially?
GATE CSE 2017 Set 1Q4MCQ1 markEasyConsider 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:
GATE CSE 2017 Set 2Q3MCQ1 markEasyDiagramMatch the algorithms with their time complexities:
GATE CSE 2017 Set 2Q30MCQ2 marksMediumConsider 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 is
GATE CSE 2017 Set 2Q38MCQ2 marksMediumConsider 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 is
GATE CSE 2016 Set 2Q39NAT2 marksMediumDiagramThe 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$ …
GATE CSE 2015 Set 1Q2MCQ1 markEasyWhich 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.
GATE CSE 2015 Set 1Q31MCQ2 marksMediumConsider 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…
GATE CSE 2015 Set 3Q4MCQ1 markMediumConsider 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 by
GATE CSE 2015 Set 3Q42MCQ2 marksMediumLet $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))$
GATE CSE 2014 Set 1Q42MCQ2 marksMediumConsider 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 * 3
GATE CSE 2014 Set 2Q13MCQ1 markEasyWhich 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$
GATE CSE 2013Q18MCQ1 markEasyWhich 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…
GATE CSE 2013Q31MCQ2 marksMediumConsider 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 is
GATE CSE 2013Q44MCQ2 marksMediumConsider 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…
GATE CSE 2012Q18MCQ1 markEasyLet 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?
GATE CSE 2011Q37MCQ2 marksMediumWhich 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}$

Topic guide

What does GATE test in Asymptotic Analysis?

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 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
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.
Loop Step Counting and Return Value Analysis
common · mixed · 2 marks · 2023, 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
common · mixed · 1 marks · 2026, 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
occasional · MSQ · 1 marks · 2026
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
occasional · MCQ · 2 marks · 2026
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+ 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)).
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.

Asymptotic Analysis

31 Qs · since 2011 · 45 marks · 1.9 marks/paperMedium yield

Take topic test

Across GATE CS exam papers, asymptotic complexity is evaluated through rigorous mathematical analysis and algorithmic code inspection. Questions consistently focus on solving recur… Guide

Type

Topic guide

What does GATE test in Asymptotic Analysis?

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
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
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.
Loop Step Counting and Return Value Analysis
common · mixed · 2 marks · 2023, 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
common · mixed · 1 marks · 2026, 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
occasional · MSQ · 1 marks · 2026
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
occasional · MCQ · 2 marks · 2026
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+ 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)).
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