chapter

Asymptotic Analysis and Recurrence Relations PYQs for GATE CS

Solve 12+ Asymptotic Analysis and Recurrence Relations previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

2026 Slot Set2 PYQ

Consider the following functions, where n is a positive integer. n^{1/3}, lo g (n), lo g (n!), 2^{l o g (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.

Question 2

2026 Slot Set2 PYQ

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity Θ (n) ?

Question 3

2026 Slot Set1 PYQ

Level 3: Exam Standard

Consider the following recurrence relations: For all n > 1, T_{1} (n) = 4 T_{1} (\frac{n}{2}) + T_{2} (n) T_{2} (n) = 5 T_{2} (\frac{n}{4}) + Θ (lo g_{2} n) Assume that for all n \leq 1, T_{1} (n) = 1 and T_{2} (n) = 1 . Which one of the following options is correct?

Question 4

2025 Slot Set1 PYQ

Consider the following recurrence relation: T (n) = 2 T (n - 1) + n 2^{n} for n > 0, T (0) = 1. Which ONE of the following options is CORRECT?

Question 5

2024 Slot Set2 PYQ

Let T (n) be the recurrence relation defined as follows: T (0) = 1, T (1) = 2, and T (n) = 5 T (n - 1) - 6 T (n - 2) for n \geq 2 Which one of the following statements is TRUE?

Question 6

2024 Slot Set1 PYQ

Level 3: Exam Standard

Consider the following recurrence relation: T (n) = {n T (n) + n 1 for n \geq 1, for n = 1. Which one of the following options is CORRECT?

Question 7

2023 PYQ

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

Question 8

2023 PYQ

Level 3: Exam Standard

Consider functions Function 1 and Function 2 expressed in pseudocode as follows: Function 1 while n&gt;1 do for i = 1 to n do x = x + 1; end for n = ⌊ n /2 ⌋; end while Function 2 for i = 1 to 100 * n do x = x + 1; end for Let f_{1} (n) and f_{2} (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?

Question 9

2022 PYQ

Which one of the following statements is TRUE for all positive functions f (n) ?

Question 10

2021 Slot Set2 PYQ

For constants a \geq 1 and b > 1, consider the following recurrence defined on the non-negative integers: T (n) = a \cdot T (\frac{n}{b}) + f (n) Which one of the following options is correct about the recurrence T (n) ?

Free preview ends here

Login to view the complete previous-year questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Asymptotic Analysis and Recurrence Relations PYQs for GATE CS

Solve 12+ Asymptotic Analysis and Recurrence Relations previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Anatomy of an Algorithmic Recurrence

An algorithmic recurrence relation expresses the running time of a recursive algorithm in terms of the running time on smaller inputs.

1. Base Case

The time complexity for the smallest possible input size (e.g., $T (1) = Θ (1)$ ).

2. Recursive Step

Time for input $n$ , expressed as the sum of time to solve smaller subproblems and time to divide/combine.

Merge Sort: $T (n) = 2 T (n /2) + Θ (n)$

The Substitution Method for Recurrences

The Substitution Method

Guess the asymptotic bound, then verify using mathematical induction.

Step 1 & 2: Guess

T (n) \leq c n lo g n

and verify base case.

Step 3: Inductive step for

T (n) = 2 T (⌊ n /2 ⌋) + n

    T(n)≤2(c2n​log2n​)+n
    T(n)≤cn(logn−1)+n
    T(n)≤cnlogn−(c−1)n
  

Since $c \geq 1$ , $- (c - 1) n \leq 0$ , proving $T (n) = O (n lo g n)$ .

Asymptotic Analysis and Recurrence Relations: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Algorithms · 2026_Set2 MCQ

Consider the following functions, where

n

is a positive integer.

n^{1/3}, lo g (n), lo g (n!), 2^{l o g (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.

A.
$lo g (n), n^{1/3}, 2^{l o g (n)}, lo g (n!)$
B.
$n^{1/3}, lo g (n), lo g (n!), 2^{l o g (n)}$
C.
$lo g (n), n^{1/3}, lo g (n!), 2^{l o g (n)}$
D.
$2^{l o g (n)}, n^{1/3}, lo g (n), lo g (n!)$

Question 2 · Algorithms · 2026_Set2 MSQ

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $Θ (n)$ ?

A.
$T (n) = T (n - 1) + 1, T (1) = 1$
B.
$T (n) = 2 T (\frac{n}{2}) + 1, T (1) = 1$
C.
$T (n) = 2 T (\frac{n}{2}) + n, T (1) = 1$
D.
$T (n) = T (n - 1) + n, T (1) = 1$

Question 3 · Algorithms · 2026_Set1 MCQ

Consider the following recurrence relations:

For all

n > 1

T_{1} (n) = 4 T_{1} (\frac{n}{2}) + T_{2} (n)

T_{2} (n) = 5 T_{2} (\frac{n}{4}) + Θ (lo g_{2} n)

Assume that for all

n \leq 1

T_{1} (n) = 1

and

T_{2} (n) = 1

.

Which one of the following options is correct?

A.
$T_{1} (n) = Θ (n^{2})$
B.
$T_{1} (n) = Θ (n^{2} lo g_{2} n)$
C.
$T_{1} (n) = Θ (n^{l o g_{4} 5})$
D.
$T_{1} (n) = Θ (n^{l o g_{4} 5} lo g_{2} n)$

Correct Answer:

Step-by-Step Solution

Key idea: This is a system of recurrence relations, recognizable because $T_{1} (n)$ depends on the solution of $T_{2} (n)$ .

Why this method applies: We must solve the recurrences sequentially, starting from the one that is self-contained ( $T_{2}$ ), find its asymptotic bound, and then substitute that bound into the other recurrence ( $T_{1}$ ).

Step 1: Solve $T_{2} (n) = 5 T_{2} (n /4) + Θ (lo g_{2} n)$ using the Master Theorem.

Step 2: Identify $a = 5, b = 4$ . The critical exponent is $lo g_{4} 5 \approx 1.16$ .

Step 3: Compare the driving function $f (n) = lo g_{2} n$ with $n^{l o g_{4} 5}$ . Since $lo g_{2} n$ grows strictly slower than any positive polynomial power of $n$ , $f (n) = O (n^{l o g_{4} 5 - ϵ})$ for some $ϵ > 0$ .

Step 4: By Case 1 of the Master Theorem, $T_{2} (n) = Θ (n^{l o g_{4} 5})$ .

Step 5: Substitute this into the first recurrence: $T_{1} (n) = 4 T_{1} (n /2) + Θ (n^{l o g_{4} 5})$ .

Step 6: Apply the Master Theorem to $T_{1} (n)$ . Here, $a = 4, b = 2$ . The critical exponent is $lo g_{2} 4 = 2$ .

Step 7: Compare the new driving function $f (n) = n^{l o g_{4} 5}$ with $n^{2}$ . Since $lo g_{4} 5 \approx 1.16 < 2$ , we have $f (n) = O (n^{2 - ϵ})$ for $ϵ \approx 0.84$ .

Step 8: By Case 1 of the Master Theorem again, the root dominates, so $T_{1} (n) = Θ (n^{l o g_{2} 4}) = Θ (n^{2})$ .

Answer: Option A is correct.

Question 4 · Algorithms · 2025_Set1 MCQ

Consider the following recurrence relation:

T (n) = 2 T (n - 1) + n 2^{n} for n > 0, T (0) = 1.

Which ONE of the following options is CORRECT?

A.
$T (n) = Θ (n^{2} 2^{n})$
B.
$T (n) = Θ (n 2^{n})$
C.
$T (n) = Θ ((lo g n)^{2} 2^{n})$
D.
$T (n) = Θ (4^{n})$

Question 5 · Algorithms · 2024_Set2 MCQ

Let $T (n)$ be the recurrence relation defined as follows:

$T (0) = 1,$

$T (1) = 2, and$

$T (n) = 5 T (n - 1) - 6 T (n - 2) for n \geq 2$

Which one of the following statements is TRUE?

A.
$T (n) = Θ (2^{n})$
B.
$T (n) = Θ (n 2^{n})$
C.
$T (n) = Θ (3^{n})$
D.
$T (n) = Θ (n 3^{n})$

Question 6 · Algorithms · 2024_Set1 MCQ

Consider the following recurrence relation:

$T (n) = {n T (n) + n 1 for n \geq 1, for n = 1.$

Which one of the following options is CORRECT?

A.
$T (n) = Θ (n lo g lo g n)$
B.
$T (n) = Θ (n lo g n)$
C.
$T (n) = Θ (n^{2} lo g n)$
D.
$T (n) = Θ (n^{2} lo g lo g n)$

Correct Answer:

Step-by-Step Solution

Key idea: This is a recurrence relation with a square root argument, recognizable because the recursive call is $T (n)$ .

Why this method applies: Standard Master Theorem does not apply directly to $n$ . We must use a change of variables to transform it into a standard divide-and-conquer recurrence.

Step 1: Let $n = 2^{m}$ . Then $n = (2^{m})^{1/2} = 2^{m /2}$ .

Step 2: Substitute this into the recurrence: $T (2^{m}) = 2^{m /2} T (2^{m /2}) + 2^{m}$ .

Step 3: Divide the entire equation by $2^{m}$ to simplify: $\frac{T ( 2 ^{m} )}{2 ^{m}} = \frac{T ( 2 ^{m /2} )}{2 ^{m /2}} + 1$ .

Step 4: Define a new function $S (m) = \frac{T ( 2 ^{m} )}{2 ^{m}}$ . The recurrence becomes $S (m) = S (m /2) + 1$ .

Step 5: This is a standard recurrence. By the Master Theorem (or simple expansion), $S (m) = Θ (lo g m)$ .

Step 6: Substitute back $m = lo g_{2} n$ . We get $S (lo g_{2} n) = Θ (lo g lo g n)$ .

Step 7: Since $S (m) = \frac{T ( n )}{n}$ , we have $\frac{T ( n )}{n} = Θ (lo g lo g n)$ , which implies $T (n) = Θ (n lo g lo g n)$ .

Answer: Option A is correct.

Question 7 · Algorithms · 2023 MSQ

Let

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?

A.
$f \in O (g)$
B.
$f \in Ω (g)$
C.
$f \in o (g)$
D.
$f \in Θ (g)$

Question 8 · Algorithms · 2023 MSQ

Consider functions Function 1 and Function 2 expressed in pseudocode as follows:

Function 1
while

n&gt;1

do
for

i = 1

n

x = x + 1;

end for

n = ⌊ n /2 ⌋;

end while

Function 2
for

i = 1

100 * n

x = x + 1;

end for

Let

f_{1} (n)

and

f_{2} (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?

A.
$f_{1} (n) \in Θ (f_{2} (n))$
B.
$f_{1} (n) \in o (f_{2} (n))$
C.
$f_{1} (n) \in ω (f_{2} (n))$
D.
$f_{1} (n) \in O (n)$

Correct Answer:

["A","D"]

Step-by-Step Solution

Key idea: This is a loop complexity analysis question, recognizable because it provides pseudocode and asks for the asymptotic relationship between the execution counts of two functions.

Why this method applies: We need to mathematically count the number of iterations for each loop structure and then compare their growth rates using asymptotic notation definitions.

Step 1: Analyze Function 1. The outer while loop halves $n$ each time. The inner for loop runs $n$ times, then $⌊ n /2 ⌋$ times, then $⌊ n /4 ⌋$ times, and so on.

Step 2: The total number of executions $f_{1} (n)$ is bounded by the geometric series: $n + \frac{n}{2} + \frac{n}{4} + \dots \leq n \sum_{i = 0}^{\infty} (\frac{1}{2})^{i} = 2 n$ .

Step 3: Thus, $f_{1} (n) = Θ (n)$ .

Step 4: Analyze Function 2. The for loop runs exactly $100 n$ times. Thus, $f_{2} (n) = 100 n$ , which is also $Θ (n)$ .

Step 5: Compare $f_{1} (n)$ and $f_{2} (n)$ . Since both are $Θ (n)$ , their ratio approaches a constant ( $2/100$ ). Therefore, $f_{1} (n) \in Θ (f_{2} (n))$ is TRUE.

Step 6: Check other options. $f_{1} (n) \in o (f_{2} (n))$ is FALSE because the limit of their ratio is not 0. $f_{1} (n) \in ω (f_{2} (n))$ is FALSE for the same reason. $f_{1} (n) \in O (n)$ is TRUE because $f_{1} (n) \leq 2 n$ .

Answer: Options A and D are true.

Question 9 · Algorithms · 2022 MCQ

Which one of the following statements is TRUE for all positive functions $f (n)$ ?

A.
$f (n^{2}) = θ (f (n)^{2})$ , when $f (n)$ is a polynomial
B.
$f (n^{2}) = o (f (n)^{2})$
C.
$f (n^{2}) = O (f (n)^{2})$ , when $f (n)$ is an exponential function
D.
$f (n^{2}) = Ω (f (n)^{2})$

Question 10 · Algorithms · 2021_Set2 MCQ

For constants

a \geq 1

and

b > 1

, consider the following recurrence defined on the non-negative integers:

T (n) = a \cdot T (\frac{n}{b}) + f (n)

Which one of the following options is correct about the recurrence

T (n)

A.
If $f (n)$ is $n lo g_{2} (n)$ , then $T (n)$ is $Θ (n lo g_{2} (n))$ .
B.
If $f (n)$ is $\frac{n}{l o g _{2} ( n )}$ , then $T (n)$ is $Θ (lo g_{2} (n))$ .
C.
If $f (n)$ is $O (n^{l o g_{b} (a) - ϵ})$ for some $ϵ > 0$ , then $T (n)$ is $Θ (n^{l o g_{b} (a)})$ .
D.
If $f (n)$ is $Θ (n^{l o g_{b} (a)})$ , then $T (n)$ is $Θ (n^{l o g_{b} (a)})$ .

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Asymptotic Analysis and Recurrence Relations PYQs for GATE CS

Anatomy of an Algorithmic Recurrence

Anatomy of an Algorithmic Recurrence

1. Base Case

2. Recursive Step

The Substitution Method for Recurrences

The Substitution Method

Asymptotic Analysis and Recurrence Relations: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit