GATE Algorithms and Data Structures 1 — Questions and Answers
Question 1: What is the worst-case time complexity of Merge Sort on an array of n elements?
- O(n)
- O(n log n) (Correct answer)
- O(n²)
- O(log n)
Correct answer: O(n log n)
Merge Sort satisfies the recurrence T(n) = 2T(n/2) + O(n), which by the Master Theorem resolves to O(n log n) in all cases.
Question 2: Which data structure is used in Breadth-First Search (BFS) to track the order in which vertices are visited?
- Stack
- Queue (Correct answer)
- Priority Queue
- Deque
Correct answer: Queue
BFS explores vertices level by level, requiring a FIFO queue so that nodes discovered earlier are processed before later-discovered nodes.
Question 3: What is the worst-case time complexity of QuickSort?
- O(n log n)
- O(n log² n)
- O(n²) (Correct answer)
- O(n³)
Correct answer: O(n²)
QuickSort's worst case occurs when the pivot is always the minimum or maximum element (e.g., already-sorted input with a fixed pivot), producing unbalanced partitions and O(n²) comparisons.
Question 4: In a randomly constructed Binary Search Tree (BST), what is the average-case time complexity for a search operation?
- O(1)
- O(log n) (Correct answer)
- O(n)
- O(n log n)
Correct answer: O(log n)
A randomly constructed BST has an expected height of O(log n), so search visits at most O(log n) nodes on average.
Question 5: What is the height of a complete binary tree containing n nodes?
- O(n)
- O(n²)
- O(log n) (Correct answer)
- O(√n)
Correct answer: O(log n)
A complete binary tree of height h has between 2^h and 2^(h+1)−1 nodes, so h = ⌊log₂ n⌋, which is O(log n).
Question 6: Which of the following sorting algorithms is both stable and guarantees O(n log n) worst-case time complexity?
- QuickSort
- HeapSort
- Merge Sort (Correct answer)
- Selection Sort
Correct answer: Merge Sort
Merge Sort preserves the relative order of equal elements (stable) and always runs in O(n log n); HeapSort is O(n log n) but not stable, and QuickSort degrades to O(n²) worst case.
Question 7: What is the time complexity of inserting an element into a max-heap containing n elements?
- O(1)
- O(log n) (Correct answer)
- O(n)
- O(n log n)
Correct answer: O(log n)
The new element is added at the last position and then sifted up through at most O(log n) levels (the height of the heap) to restore the heap property.
GATE Algorithms and Data Structures 1
What is the worst-case time complexity of Merge Sort on an array of n elements?