Asymptotic Analysis and Time/Space Complexity: GATE CS previous year questions (Algorithms)

Hide the 1 question not in the current syllabus

GATE CS 2026 Set 1MCQ1 markMedium (estimate)
GATE CS 2026 Set 1, Q.17
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)$ Ass...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2026 Set 2MCQ1 markEasy (estimate)
GATE CS 2026 Set 2, Q.24
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 fun...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2026 Set 2MSQ1 markEasy (estimate)
GATE CS 2026 Set 2, Q.25
Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $Θ (n)$ ?
Asymptotic Analysis and Time/Space Complexity
GATE CS 2025 Set 1MCQ1 markEasy (estimate)
GATE CS 2025 Set 1, Q.20
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?
Asymptotic Analysis and Time/Space Complexity
GATE CS 2024 Set 1MCQ1 markEasy (estimate)
GATE CS 2024 Set 1, Q.17
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 t...
Asymptotic Analysis and Time/Space Complexity · Searching and Sorting Algorithms
GATE CS 2024 Set 1MCQ2 marksMedium (estimate)
GATE CS 2024 Set 1, Q.42
Consider the following recurrence relation: $T (n) = {n T (n) + n 1 for n \geq 1, for n = 1.$ Which one of the follow...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2024 Set 2MCQ1 markMedium (estimate)
GATE CS 2024 Set 2, Q.15
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?
Asymptotic Analysis and Time/Space Complexity · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2023MSQ1 markEasy (estimate)
GATE CS 2023, Q.29
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?
Asymptotic Analysis and Time/Space Complexity
GATE CS 2023MSQ2 marksEasy (estimate)
GATE CS 2023, Q.54
Consider functions Function 1 and Function 2 expressed in pseudocode as follows: Function 1 Function 2 while n > 1 do for i = 1 to 100 * n do for i = 1 to n do x = x + 1; x...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2022MCQ1 markEasy (estimate)
GATE CS 2022, Q.11
Which one of the following statements is TRUE for all positive functions $f (n)$ ?
Asymptotic Analysis and Time/Space Complexity
GATE CS 2021 Set 1MCQ1 markEasy (estimate)
GATE CS 2021 Set 1, Q.13 (CS Q.3)
Consider the following three functions. $f_{1} = 1 0^{n}, f_{2} = n^{l o g n}, f_{3} = n^{n}$ Which one of the following options arranges the functions in the increas...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2021 Set 1MCQ2 marksMedium (estimate)
GATE CS 2021 Set 1, Q.40 (CS Q.30)
Consider the following recurrence relation. $T (n) = {T (n /2) + T (2 n /5) + 7 n 1 if n > 0 if n = 0$ Which one of the following opti...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2021 Set 2MCQ2 marksEasy (estimate)
GATE CS 2021 Set 2, Q.49 (CS Q.39)
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...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2020MCQ1 markMedium (estimate)
GATE CS 2020, Q.12 (CS Q.2)
For parameters $a$ and $b$ , both of which are $ω (1)$ , $T (n) = T (n^{1/ a}) + 1$ , and $T (b) = 1$ . Then $T (n)$ is
Asymptotic Analysis and Time/Space Complexity
GATE CS 2020MCQ1 markMedium (estimate)
GATE CS 2020, Q.16 (CS Q.6)
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially?
Binary Trees, Binary Search Trees and Balanced Trees · Asymptotic Analysis and Time/Space Complexity
GATE CS 2020MCQ1 markEasy (estimate)
GATE CS 2020, Q.26 (CS Q.16)
What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?
Arrays and Linked Lists · Asymptotic Analysis and Time/Space Complexity
GATE CS 2020MCQ2 marksEasy (estimate)
GATE CS 2020, Q.51 (CS Q.41)
In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a, b]$ ? Assume that the number of reported elemen...
Binary Trees, Binary Search Trees and Balanced Trees · Asymptotic Analysis and Time/Space Complexity
GATE CS 2017 Set 1MCQ1 markEasy (estimate)
GATE CS 2017 Set 1, Q.4 (CS Q.4)
Consider the following functions from positive integers to real numbers: $10, n, n, lo g_{2} n, \frac{100}{n}$ The CORRECT arrangement of the abov...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2017 Set 2MCQ1 markEasy (estimate)
GATE CS 2017 Set 2, Q.3 (CS Q.3)
Match the algorithms with their time complexities: | Algorithm | Time complexity | | :--- | :--- | | (P) Towers of Hanoi with $n$ disks | (i) $Θ (n^{2})$ | | (Q) Binary search...
Asymptotic Analysis and Time/Space Complexity · Searching and Sorting Algorithms
GATE CS 2017 Set 2MCQ2 marksMedium (estimate)
GATE CS 2017 Set 2, Q.30 (CS Q.30)
Consider the recurrence function $T (n) = {2 T (n) + 1, 2, n > 2 0 < n \leq 2$ Then $T (n)$ in terms of $Θ$ notation is
Asymptotic Analysis and Time/Space Complexity
GATE CS 2017 Set 2MCQ2 marksMedium (estimate)
GATE CS 2017 Set 2, Q.38 (CS Q.38)
Consider 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…
Asymptotic Analysis and Time/Space Complexity
GATE CS 2016 Set 2NAT2 marksHard (estimate)
GATE CS 2016 Set 2, Q.49 (CS Q.39)
The given diagram shows the flowchart for a recursive function $A (n)$ . Assume that all statements, except for the recursive calls, have $O (1)$ time complexity. If the worst case...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2016 Set 2MCQ2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.51 (CS Q.41)
In an adjacency list representation of an undirected simple graph $G = (V, E)$ , each edge $(u, v)$ has two adjacency list entries: $[v]$ in the adjacency list of $u$ , and $[u]$ ...
Graph Representations and Disjoint Sets · Asymptotic Analysis and Time/Space Complexity
GATE CS 2015 Set 1MCQ1 markEasy (estimate)
GATE CS 2015 Set 1, Q.12 (CS Q.2)
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting $n$ ( $n \geq 2$ ) numbers? In the recurrence equati...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2015 Set 1MCQ2 marksMedium (estimate)
GATE CS 2015 Set 1, Q.41 (CS Q.31)
Consider 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...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2015 Set 2MCQ1 markMedium (estimate)
GATE CS 2015 Set 2, Q.12 (CS Q.2)
Consider two decision problems $Q_{1}, Q_{2}$ such that $Q_{1}$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_{2}$ . Then which one of the following is c...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2015 Set 3MCQ1 markEasy (estimate)
GATE CS 2015 Set 3, Q.14 (CS Q.4)
Consider the equality $\sum_{i = 0}^{n} i^{3} = X$ and the following choices for $X$ …
Asymptotic Analysis and Time/Space Complexity
GATE CS 2015 Set 3MCQ2 marksMedium (estimate)
GATE CS 2015 Set 3, Q.37 (CS Q.27)
Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a proble...
Searching and Sorting Algorithms · Asymptotic Analysis and Time/Space Complexity
GATE CS 2015 Set 3MCQ2 marksMedium (estimate)
GATE CS 2015 Set 3, Q.52 (CS Q.42)
Let $f (n) = n$ and $g (n) = n^{1 + s i n n}$ , where $n$ is a positive integer. Which of the following statements is/are correct? I. $f (n) = O (g (n))$ II. $f (n) = Ω (g (n))$
Asymptotic Analysis and Time/Space Complexity
GATE CS 2015 Set 3NAT2 marksEasy (estimate)
GATE CS 2015 Set 3, Q.59 (CS Q.49)
Suppose $c = (c [0], \dots, c [k - 1])$ is an array of length $k$ , where all the entries are from the set ${0, 1}$ . For any positive integers $a$ and $n$ , consider the following...
Combinatorics, Counting, Recurrence Relations and Generating Functions · Asymptotic Analysis and Time/Space Complexity
GATE CS 2015 Set 3MCQ2 marksMedium (estimate)
GATE CS 2015 Set 3, Q.63 (CS Q.53)
Language $L_{1}$ is polynomial time reducible to language $L_{2}$ . Language $L_{2}$ is polynomial time reducible to $L_{3}$ , which in turn is polynomial time reducible to language $L_{4}$ ...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2014 Set 1MCQ2 marksMedium (estimate)
GATE CS 2014 Set 1, Q.52 (CS Q.42)
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 *...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2014 Set 2MCQ1 markEasy (estimate)
GATE CS 2014 Set 2, Q.23 (CS Q.13)
Which one of the following correctly determines the solution of the recurrence relation with $T (1) = 1$ ? $T (n) = 2 T (\frac{n}{2}) + lo g n$
Asymptotic Analysis and Time/Space Complexity
GATE CS 2014 Set 3NAT1 markMedium (estimate)
GATE CS 2014 Set 3, Q.21 (CS Q.11)
The minimum number of arithmetic operations required to evaluate the polynomial $P (X) = X^{5} + 4 X^{3} + 6 X + 5$ for a given value of $X$ , using only one temporary variable is _____.
Asymptotic Analysis and Time/Space Complexity
GATE CS 2014 Set 3MCQ2 marksEasy (estimate)
GATE CS 2014 Set 3, Q.48 (CS Q.38)
Consider the decision problem 2CNFSAT defined as follows: ${Φ ∣ Φ is a satisfiable propositional formula in CNF with at most two literals per clause}$ For e...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2012MCQ1 markEasy (estimate)
GATE CS 2012, Q.4 (CS Q.4)
Assuming $P \neq = NP$ , which of the following is TRUE?
Asymptotic Analysis and Time/Space Complexity
GATE CS 2012MCQ1 markEasy (estimate)
GATE CS 2012, Q.16 (CS Q.16)
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with $n$ discs is
Divide and Conquer · Asymptotic Analysis and Time/Space Complexity
GATE CS 2012MCQ1 markEasy (estimate)
GATE CS 2012, Q.18 (CS Q.18)
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?
Asymptotic Analysis and Time/Space Complexity
GATE CS 2012MCQ2 marksMedium (estimate)
GATE CS 2012, Q.39 (CS Q.39)
A list of $n$ strings, each of length $n$ , is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
Searching and Sorting Algorithms · Asymptotic Analysis and Time/Space Complexity
GATE CS 2011MCQ1 markMedium (estimate)Not in current syllabus
GATE CS 2011, Q.5 (CS Q.5)
A company needs to develop a strategy for software product development for which it has a choice of two programming languages L1 and L2. The number of lines of code (LOC) develo...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2011MCQ1 markMedium (estimate)
GATE CS 2011, Q.7 (CS Q.7)
A company needs to develop digital signal processing software for one of its newest inventions. The software is expected to have 40000 lines of code. The company needs to determ...
Asymptotic Analysis and Time/Space Complexity
GATE CS 2011MCQ2 marksMedium (estimate)
GATE CS 2011, Q.37 (CS Q.37)
Which of the given options provides the increasing order of asymptotic complexity of functions $f_{1}, f_{2}, f_{3}$ and $f_{4}$ ?…
Asymptotic Analysis and Time/Space Complexity

Questions

Other topics of Algorithms