Algorithms Sorting & Searching Algorithms 2 — Questions and Answers
Question 1: What is the space complexity of MergeSort?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n²)
Correct answer: O(n)
MergeSort requires O(n) auxiliary space to hold the temporary arrays used during the merge step.
Question 2: In HeapSort, what data structure is used to sort elements?
- Binary Search Tree
- Max-Heap (Correct answer)
- Stack
- Queue
Correct answer: Max-Heap
HeapSort builds a max-heap from the input and repeatedly extracts the maximum element to sort the array.
Question 3: What is the time complexity of Counting Sort when the range of elements is k?
- O(n log n)
- O(n + k) (Correct answer)
- O(nk)
- O(k log k)
Correct answer: O(n + k)
Counting Sort runs in O(n + k) time by counting occurrences of each element and then reconstructing the sorted array.
Question 4: Which search algorithm requires the input list to be sorted before it can be applied?
- Linear Search
- Jump Search
- Ternary Search
- Binary Search (Correct answer)
Correct answer: Binary Search
Binary Search requires a sorted array because it relies on comparing the midpoint value to determine which half to discard.
Question 5: What distinguishes an in-place sorting algorithm from others?
- It sorts faster than O(n log n)
- It uses only a constant amount of extra memory (Correct answer)
- It preserves the original array
- It works only on integers
Correct answer: It uses only a constant amount of extra memory
An in-place algorithm rearranges elements using O(1) extra memory beyond the input array itself.
Question 6: What is the best-case time complexity of QuickSort?
- O(n²)
- O(n)
- O(n log n) (Correct answer)
- O(log n)
Correct answer: O(n log n)
In the best case, QuickSort's pivot always divides the array into two equal halves, yielding O(n log n) performance.
Algorithms Sorting & Searching Algorithms 2
What is the space complexity of MergeSort?