GATE Algorithms: Asymptotic Analysis and Time/Space Complexity – Previous Year Questions
47 GATE previous year questions on Asymptotic Analysis and Time/Space Complexity (Algorithms, Computer Science) with answers and explanations, from every paper.
47 questions worth 74 marks in all (20 1-mark, 27 2-mark). Asked between 2007 and 2026, so you can see how the topic has been tested over time.
- GATE 2007 CS Q15 – For n>0, how many comparisons are made in this loop?
- GATE 2007 CS Q44 – Let n≥m. How many recursive calls does this C function make?
- GATE 2007 CS Q45 – Find the time complexity.
- GATE 2007 CS Q51 – Let T(n) count loop executions in this C code. Which is TRUE?
- GATE 2008 CS Q39 – Let f(n)=2n, g(n)=n!, h(n)=n n. Which asymptotic statement is true?
- GATE 2008 CS Q74 – Consider the C functions (assume N>n): What are the running times of f1(n), f2(n)?
- GATE 2009 CS Q35 – For a constant c, T(n)=n for n3, and T(n)=T(n/3)+cn otherwise. What is the time complexity?
- GATE 2021 CS (CS2) Q49 – For constants a≥1,b>1, T(n)=aT(n/b)+f(n). Which general claim is correct, under the usual positive constant base-case assumptions?
- GATE 2015 CS (CS3) Q20 – For i=0n i3=X, consider I (n4), II (n5), III O(n5), IV (n3). Which may replace X?
- GATE 2015 CS (CS3) Q37 – Worst-case mergesort takes 30 seconds for input size 64. Which best approximates the maximum size sortable in six minutes?
- GATE 2015 CS (CS3) Q41 – L1≤pL2, L3≤pL2 and L2≤pL4. Which are guaranteed? I: L4∈P implies L2∈P. II: L1∈P or L3∈P implies L2∈P. III: L1∈P iff L3∈P. IV: L4∈P implies L1,L3∈P.
- GATE 2015 CS (CS3) Q64 – For positive integer n, f(n)=n and g(n)=n1+ n. Which hold? I: f=O(g). II: f=Ω(g).
- GATE 2015 CS (CS2) Q16 – An unordered list contains n distinct elements. How many comparisons are needed to find any element that is neither its maximum nor minimum? Assume…
- GATE 2015 CS (CS2) Q26 – Decision problem Q1 reduces in polynomial time to 3-SAT, and 3-SAT reduces in polynomial time to Q2. Which conclusion is consistent with these…
- GATE 2010 CS Q22 – Packages A,B process n=10k database records. A needs 0.0001n² time; B needs 10n 10n. Find the smallest integer k for which B is faster.
- GATE 2011 CS Q47 – Find increasing asymptotic growth order for f 1(n)=2n, f 2(n)=n3/2, f 3(n)=n 2n, f 4(n)=n 2n.
- GATE 2013 CS Q40 – How many elements can heap sort sort in ( n) time?
- GATE 2013 CS Q41 – What is the asymptotic return value, rather than running time?
- GATE 2012 CS Q15 – Find the worst-case search time in a balanced BST with n2n elements.
- GATE 2012 CS Q28 – W(n) and A(n) are worst-case and average running times on inputs of size n. Which always holds?
- GATE 2017 CS (CS2) Q13 – Match (P) Towers of Hanoi with n disks, (Q) binary search on n sorted numbers, (R) worst-case heap sort on n numbers, (S) addition of two n×n…
- GATE 2017 CS (CS2) Q40 – T(n)=2T( n)+1 for n>2, and T(n)=2 for 0<n≤2. Find its asymptotic order.
- GATE 2017 CS (CS2) Q48 – Find the time complexity.
- GATE 2016 CS (CS2) Q49 – The flowchart defines recursive function A(n). Other statements cost O(1). If worst-case time is O(n), find the least α to two decimal places.
- GATE 2014 CS (CS3) Q21 – Find the minimum arithmetic operations needed to evaluate P(X)=X5+4X3+6X+5 for given X, using only one temporary variable.
- GATE 2014 CS (CS1) Q48 – A polynomial-time algorithm correctly computing the largest clique of any graph is discovered. Which Venn diagram represents P, NP and NP Complete…
- GATE 2014 CS (CS1) Q52 – Find the total multiplications in this pseudocode (inclusive loop bounds): D = 2 for i = 1 to n for j = i to n for k = j + 1 to n D = D * 3
- GATE 2017 CS (CS1) Q14 – Consider the following functions from positive integers to real numbers: 10, n, n, 2 n, 100n. The CORRECT arrangement of the above functions in…
- GATE 2015 CS (CS1) Q60 – An algorithm performs ( N)1/2 find operations, N insert operations, ( N)1/2 delete operations, and ( N)1/2 decrease-key operations on a set of data…
- GATE 2015 CS (CS1) Q64 – Consider the following C function. Which one of the following most closely approximates the return value of the function `fun1`?
- GATE 2019 CS Q47 – There are n unsorted arrays: A 1,A 2,,A n. Assume that n is odd. Each of A 1,A 2,,A n contains n distinct elements. There are no common elements…
- GATE 2026 CS (CS2) Q24 – Consider the following functions, where n is a positive integer: n1/3, n, (n!), and 2 n. Which one of the following options lists the functions in…
- GATE 2026 CS (CS2) Q25 – Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity (n)?
- GATE 2026 CS (CS2) Q38 – Consider an array A of integers of size n with indices from 1 to n. An algorithm is to be designed to check whether A satisfies i,j \1,,n-1\ such that…
- GATE 2026 CS (CS1) Q17 – Consider the following recurrence relations: For all n > 1: T 1(n) = 4T 1(n/2) + T 2(n) T 2(n) = 5T 2(n/4) + ( 2 n) Assume that for all n 1, T 1(n) =…
- GATE 2026 CS (CS1) Q47 – Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V' V such that for every (u, v) E, u V' or v V'. Let the size of the…
- GATE 2025 CS (CS1) Q20 – Consider the following recurrence relation: T(n) = 2T(n-1) + n2n for n > 0, T(0) = 1. Which ONE of the following options is CORRECT?
- GATE 2024 CS (CS2) Q15 – 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…
- GATE 2024 CS (CS1) Q17 – 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…
- GATE 2024 CS (CS1) Q42 – Consider the recurrence T(n)=n\,T(n)+n for n 1... with T(1)=1. Which one of the following options is CORRECT?
- GATE 2023 CS Q29 – Let f and g be functions of natural numbers given by f(n) = n and g(n) = n2. Which of the following statements is/are TRUE?
- GATE 2023 CS Q54 – Consider functions Function 1 and Function 2 expressed in pseudocode as follows: Let f 1(n) and f 2(n) denote the number of times the statement "x = x…
- GATE 2022 CS Q11 – Which one of the following statements is TRUE for all positive functions f(n)?
- GATE 2022 CS Q51 – Consider the following recurrence: f(1)=1; f(2n)=2f(n)-1, for n1; f(2n+1)=2f(n)+1, for n1. Then, which of the following statements is/are TRUE?
- GATE 2021 CS (CS1) Q13 – Consider the following three functions. f 1 = 10n, f 2 = n n, f 3 = nn Which one of the following options arranges the functions in the increasing…
- GATE 2021 CS (CS1) Q40 – Consider the following recurrence relation. T(n) = T(n/2) + T(2n/5) + 7n if n>0; T(n)=1 if n=0. Which one of the following options is correct?
- GATE 2020 CS Q12 – For parameters a and b, both of which are (1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is