Previous Year GATE Questions

1. 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? More than one answer may be correct. [GATE CSE 2020]

(A) Θ(n)

(B) Θ(n log n)

(C) Θ(n²)

(D) Θ(1)

Solution: Correct answer is (C)

2. What is the worst-case time complexity of inserting n² elements into an AVL tree with n elements initially? [GATE CSE 2020]

(A) Θ(n⁴)

(B) Θ(n²)

(C) Θ(n² log n)

(D) Θ(n³)

Solution: Correct answer is (C)

3. Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4? [GATE CSE 2011]
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)

(A) f3, f2, f4, f1
(B) f3, f2, f1, f4
(C) f2, f3, f1, f4
(D) f2, f3, f4, f1

Answer: (A)
Explanation: nLogn is the slowest growing function, then comes n^(3/2), then n^(Logn).  Finally, 2^n is the fastest growing function.

4. Which one of the following statements is TRUE for all positive functions f(n)? [GATE CSE 2022]

(A) f(n²) = θ(f(n)²), when f(n) is a polynomial
(B) f(n²) = o(f(n)²)
(C) f(n²) = O(f(n)²), when f(n) is an exponential function
(D) f(n²) = Ω(f(n)²)

Solution: Correct answer is (A)

5.The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of [GATE CSE 2004]

(A) n
(B) n²
(C) n log n
(D) n log² n

Solution: Correct answer is (C)

6. Consider the following functions from positives integers to real numbers

10, √n, n, log₂n, 100/n.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
(A) log₂n, 100/n, 10, √n, n
(B) 100/n, 10, log₂n, √n, n
(C) 10, 100/n ,√n, log₂n, n
(D) 100/n, log₂n, 10 ,√n, n

Answer: (B)

Explanation: For the large number, value of inverse of number is less than a constant and value of constant is less than value of square root.

10 is constant, not affected by value of n.
√n Square root and log₂n is logarithmic. So log₂n is definitely less than √n
n has linear growth and 100/n grows inversely with value of n. For bigger value of n, we can consider it 0, so 100/n is least and n is max.

7. Consider the following three claims

1. (n + k)^m = Θ(n^m), where k and m are constants

2. 2^{n + 1} = O(2ⁿ)

3. 2^{2n + 1} = O(2ⁿ)

Which of these claims are correct ?

(A) 1 and 2
(B) 1 and 3
(C) 2 and 3
(D) 1, 2, and 3

Answer: (A)

Explanation: (n + k)^m and Θ(n^m) are asymptotically same as theta notation can always be written by taking the leading order term in a polynomial expression.

2^{n + 1} and O(2ⁿ) are also asymptotically same as 2^{n + 1} can be written as 2 * 2ⁿ and constant multiplication/addition doesn’t matter in theta notation.

2^{2n + 1} and O(2ⁿ) are not same as constant is in power.

8. Consider the following three functions.

f1 = 10ⁿ
f2 = n^logn
f3 = n^√n

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
(A) f3,f2,f1
(B) f2,f1,f3
(C) f1,f2,f3
(D) f2,f3,f1

Answer: (D)

Explanation: On comparing power of these given functions :
f1 has n in power.
f2 has logn in power.
f3 has √n in power.

Hence, f2, f3, f1 is in increasing order.

Note that you can take the log of each function then compare.

This Asymptotic Analysis of Algorithms is a critical topic for the GATE (Graduate Aptitude Test in Engineering) exam, especially for candidates in computer science and related fields. This set of notes provides an in-depth understanding of how algorithms behave as input sizes grow and is fundamental for assessing their efficiency. Let’s delve into an introduction for these notes: