GATE Algorithms: Asymptotic Analysis and Time/Space Complexity – Previous Year Questions
20 GATE previous year questions on Asymptotic Analysis and Time/Space Complexity (Algorithms, Computer Science) with answers and explanations, from every paper.
- GATE 2017 CS 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 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 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 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 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