The GATE Grind

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.

  1. GATE 2007 CS Q15 (1 mark, Multiple choice) – For n>0, how many comparisons are made in this loop?
  2. GATE 2007 CS Q44 (2 marks, Multiple choice) – Let n≥m. How many recursive calls does this C function make?
  3. GATE 2007 CS Q45 (2 marks, Multiple choice) – Find the time complexity.
  4. GATE 2007 CS Q51 (2 marks, Multiple choice) – Let T(n) count loop executions in this C code. Which is TRUE?
  5. GATE 2008 CS Q39 (2 marks, Multiple choice) – Let f(n)=2n, g(n)=n!, h(n)=n n. Which asymptotic statement is true?
  6. GATE 2008 CS Q74 (2 marks, MTA) – Consider the C functions (assume N>n): What are the running times of f1(n), f2(n)?
  7. GATE 2009 CS Q35 (2 marks, Multiple choice) – For a constant c, T(n)=n for n3, and T(n)=T(n/3)+cn otherwise. What is the time complexity?
  8. GATE 2021 CS (CS2) Q49 (2 marks, Multiple choice) – 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?
  9. GATE 2015 CS (CS3) Q20 (1 mark, Multiple choice) – For i=0n i3=X, consider I (n4), II (n5), III O(n5), IV (n3). Which may replace X?
  10. GATE 2015 CS (CS3) Q37 (2 marks, Multiple choice) – Worst-case mergesort takes 30 seconds for input size 64. Which best approximates the maximum size sortable in six minutes?
  11. GATE 2015 CS (CS3) Q41 (2 marks, Multiple choice) – 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.
  12. GATE 2015 CS (CS3) Q64 (2 marks, Multiple choice) – For positive integer n, f(n)=n and g(n)=n1+ n. Which hold? I: f=O(g). II: f=Ω(g).
  13. GATE 2015 CS (CS2) Q16 (1 mark, Multiple choice) – An unordered list contains n distinct elements. How many comparisons are needed to find any element that is neither its maximum nor minimum? Assume…
  14. GATE 2015 CS (CS2) Q26 (1 mark, Multiple choice) – 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…
  15. GATE 2010 CS Q22 (1 mark, Multiple choice) – 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.
  16. GATE 2011 CS Q47 (2 marks, Multiple choice) – 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.
  17. GATE 2013 CS Q40 (2 marks, Multiple choice) – How many elements can heap sort sort in ( n) time?
  18. GATE 2013 CS Q41 (2 marks, Multiple choice) – What is the asymptotic return value, rather than running time?
  19. GATE 2012 CS Q15 (1 mark, Multiple choice) – Find the worst-case search time in a balanced BST with n2n elements.
  20. GATE 2012 CS Q28 (1 mark, Multiple choice) – W(n) and A(n) are worst-case and average running times on inputs of size n. Which always holds?
  21. GATE 2017 CS (CS2) Q13 (1 mark, Multiple choice) – 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…
  22. GATE 2017 CS (CS2) Q40 (2 marks, Multiple choice) – T(n)=2T( n)+1 for n>2, and T(n)=2 for 0<n≤2. Find its asymptotic order.
  23. GATE 2017 CS (CS2) Q48 (2 marks, Multiple choice) – Find the time complexity.
  24. GATE 2016 CS (CS2) Q49 (2 marks, Numerical answer) – 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.
  25. GATE 2014 CS (CS3) Q21 (1 mark, Numerical answer) – Find the minimum arithmetic operations needed to evaluate P(X)=X5+4X3+6X+5 for given X, using only one temporary variable.
  26. GATE 2014 CS (CS1) Q48 (2 marks, Multiple choice) – A polynomial-time algorithm correctly computing the largest clique of any graph is discovered. Which Venn diagram represents P, NP and NP Complete…
  27. GATE 2014 CS (CS1) Q52 (2 marks, Multiple choice) – 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
  28. GATE 2017 CS (CS1) Q14 (1 mark, Multiple choice) – Consider the following functions from positive integers to real numbers: 10, n, n, 2 n, 100n. The CORRECT arrangement of the above functions in…
  29. GATE 2015 CS (CS1) Q60 (2 marks, Multiple choice) – 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…
  30. GATE 2015 CS (CS1) Q64 (2 marks, Multiple choice) – Consider the following C function. Which one of the following most closely approximates the return value of the function `fun1`?
  31. GATE 2019 CS Q47 (2 marks, Multiple choice) – 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…
  32. GATE 2026 CS (CS2) Q24 (1 mark, Multiple choice) – 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…
  33. GATE 2026 CS (CS2) Q25 (1 mark, Multiple select) – Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity (n)?
  34. GATE 2026 CS (CS2) Q38 (2 marks, Multiple choice) – 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…
  35. GATE 2026 CS (CS1) Q17 (1 mark, Multiple choice) – 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) =…
  36. GATE 2026 CS (CS1) Q47 (2 marks, Multiple choice) – 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…
  37. GATE 2025 CS (CS1) Q20 (1 mark, Multiple choice) – 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?
  38. GATE 2024 CS (CS2) Q15 (1 mark, Multiple choice) – 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…
  39. GATE 2024 CS (CS1) Q17 (1 mark, Multiple choice) – 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…
  40. GATE 2024 CS (CS1) Q42 (2 marks, Multiple choice) – Consider the recurrence T(n)=n\,T(n)+n for n 1... with T(1)=1. Which one of the following options is CORRECT?
  41. GATE 2023 CS Q29 (1 mark, Multiple select) – 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?
  42. GATE 2023 CS Q54 (2 marks, Multiple select) – 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…
  43. GATE 2022 CS Q11 (1 mark, Multiple choice) – Which one of the following statements is TRUE for all positive functions f(n)?
  44. GATE 2022 CS Q51 (2 marks, Multiple select) – 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?
  45. GATE 2021 CS (CS1) Q13 (1 mark, Multiple choice) – 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…
  46. GATE 2021 CS (CS1) Q40 (2 marks, Multiple choice) – 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?
  47. GATE 2020 CS Q12 (1 mark, Multiple choice) – For parameters a and b, both of which are (1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is