Algorithms Sorting & Searching Algorithms 1 — Questions and Answers
Question 1: What is the average-case time complexity of QuickSort?
- O(n log n) (Correct answer)
- O(n²)
- O(n)
- O(log n)
Correct answer: O(n log n)
QuickSort achieves O(n log n) average-case complexity by recursively partitioning the array around a pivot element.
Question 2: Which sorting algorithm is considered stable and has a guaranteed worst-case time complexity of O(n log n)?
- QuickSort
- HeapSort
- MergeSort (Correct answer)
- SelectionSort
Correct answer: MergeSort
MergeSort is stable and guarantees O(n log n) in all cases by dividing the array into halves and merging them in sorted order.
Question 3: What is the time complexity of Binary Search on a sorted array of n elements?
- O(n)
- O(log n) (Correct answer)
- O(n log n)
- O(1)
Correct answer: O(log n)
Binary Search eliminates half the remaining elements at each step, yielding O(log n) time complexity.
Question 4: Which sorting algorithm has the best performance on nearly sorted data?
- MergeSort
- QuickSort
- HeapSort
- Insertion Sort (Correct answer)
Correct answer: Insertion Sort
Insertion Sort runs in O(n) time on nearly sorted data because few elements need to be moved.
Question 5: What is the worst-case time complexity of Bubble Sort?
- O(n log n)
- O(n)
- O(n²) (Correct answer)
- O(log n)
Correct answer: O(n²)
Bubble Sort has O(n²) worst-case complexity because it compares adjacent pairs across n passes of the array.
Question 6: Which algorithm finds the k-th smallest element in an unsorted array in average O(n) time?
- Binary Search
- MergeSort
- QuickSelect (Correct answer)
- HeapSort
Correct answer: QuickSelect
QuickSelect uses partitioning like QuickSort but only recurses into the partition containing the target element, achieving average O(n) time.
Algorithms Sorting & Searching Algorithms 1
What is the average-case time complexity of QuickSort?