T(n) = aT(n/b) + Θ(nᵏ logᵖ n): log_b a > k → Θ(n^(log_b a)); = k → Θ(nᵏ logᵖ⁺¹ n); < k → Θ(nᵏ logᵖ n)
Stirling
log(n!) = Θ(n log n); n! = Θ(√n (n/e)ⁿ)
Log rules
log_a b = log_c b / log_c a, so all log bases differ by a constant factor. 2^(log₂ n) = n
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Order functions by asymptotic growth
Rank f(n) like n^(log n), 2^(√n), n!, (log n)^(log n) and pick the correct increasing order.
★★★
Time complexity of a nested loop / recursive code
Count iterations; watch for doubling variables and inner bounds that depend on the outer index.
★★★
Solve a recurrence
Master theorem or recursion tree, including T(n) = T(√n) + 1 and unequal splits.
★★★
True or false: f = O(g), f = Θ(g)
Compare exponentials with polynomials, and log bases inside exponents (2^(2n) vs 2^n).
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
16 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
16 questions · 0 correct of 0 attempted · marks 0 / 22
Year:
GATE 2025 CS1 · Q20MCQ1 mark
Consider the following recurrence relation: T(n) = 2T(n − 1) + n·2n for n > 0, T(0) = 1. Which ONE of the following options is CORRECT?
GATE 2024 CS2 · Q15MCQ1 mark
Let T(n) be the recurrence relation defined as follows: T(0) = 1, T(1) = 2, and T(n) = 5T(n − 1) − 6T(n − 2) for n ≥ 2. Which one of the following statements is TRUE?
GATE 2024 CS1 · Q17MCQ1 mark
Given 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 2024 CS1 · Q42MCQ2 marks
Consider the following recurrence relation: T(n) = √n · T(√n) + n for n ≥ 1 (with T(1) = 1). Which one of the following options is CORRECT?
GATE 2023 · Q29MSQ1 mark
Let f and g be functions of natural numbers given by f(n) = n and g(n) = n². Which of the following statements is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2023 · Q54MSQ2 marks
Consider functions Function 1 and Function 2 expressed in pseudocode as follows. Function 1: while n > 1 do { for i = 1 to n do x = x + 1; n = ⌊n/2⌋ }. Function 2: for i = 1 to 100·n do x = x + 1. 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?
One or more options may be correct. Select all that apply, then submit.
GATE 2022 · Q11MCQ1 mark
Which one of the following statements is TRUE for all positive functions f(n)?
GATE 2022 · Q51MSQ2 marks
Consider the following recurrence: f(1) = 1; f(2n) = 2f(n) − 1, for n ≥ 1; f(2n + 1) = 2f(n) + 1, for n ≥ 1. Then, which of the following statements is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q3MCQ1 mark
Consider the following three functions: f1 = 10n, f2 = nlog n, f3 = n√n. Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
GATE 2020 · Q2MCQ1 mark
For parameters a and b, both of which are ω(1), T(n) = T(n1/a) + 1, and T(b) = 1. Then T(n) is
GATE 2017 Set 1 · Q4MCQ1 mark
Consider the following functions from positive integers to real numbers: 10, √n, n, log2 n, 100/n. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
GATE 2016 Set 1 · Q27NAT2 marks
Consider the recurrence relation a1 = 8, an = 6n² + 2n + an−1. Let a99 = K × 104. The value of K is ______.
GATE 2014 Set 1 · Q42MCQ2 marks
Consider 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 2013 Code A · Q31MCQ2 marks
Consider 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 2012 Code A · Q16MCQ1 mark
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
GATE 2012 Code A · Q18MCQ1 mark
Let 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?
Common traps
2^(2n) is not O(2ⁿ) (it equals 4ⁿ), but 2^(n + 1) is. Constants in the exponent matter.
log(n!) is Θ(n log n) but n! itself is far bigger than any exponential cⁿ.
The Master theorem needs a constant a and b: T(n) = 2ⁿT(n/2) + nⁿ is outside it.
Big-O is an upper bound only: saying "quick sort is O(n³)" is true but useless.