Sorting and Searching MCQs, Set 1 of 1
Q1 / 16
Q1. What is the worst-case time complexity of binary search?
- A.O(1)
- B.O(log n)(correct answer)
- C.O(n)
- D.O(n log n)
Each step halves the search range.
Q2. Binary search requires the array to be:
- A.Sorted(correct answer)
- B.Of even length
- C.Stored in a linked list
- D.Free of negative numbers
Comparing with the middle element only tells you which half to keep if the data is sorted.
Q3. What is the average-case time complexity of quicksort?
- A.O(n)
- B.O(n log n)(correct answer)
- C.O(n²)
- D.O(log n)
On average the pivot splits the array into reasonably balanced parts.
Q4. What is the worst-case time complexity of quicksort?
- A.O(n log n)
- B.O(n)
- C.O(n²)(correct answer)
- D.O(2^n)
This happens when the pivot is always the smallest or largest element.
Q5. Which sorting algorithm is guaranteed O(n log n) in the worst case?
- A.Quicksort
- B.Merge sort(correct answer)
- C.Insertion sort
- D.Bubble sort
Merge sort always splits in half and merges in linear time.
Q6. Which of these sorting algorithms is stable?
- A.Merge sort(correct answer)
- B.Heap sort
- C.Quicksort (in-place version)
- D.Selection sort
A stable sort keeps equal elements in their original relative order; merge sort does this.
Q7. Insertion sort runs in O(n) time when the input is:
- A.Reverse sorted
- B.Already sorted(correct answer)
- C.Random
- D.All distinct
Each new element is compared once and stays where it is.
Q8. How many comparisons does linear search make in the worst case for n elements?
- A.1
- B.log n
- C.n(correct answer)
- D.n²
It may have to check every element.
Q9. Which algorithm repeatedly swaps adjacent elements that are in the wrong order?
- A.Selection sort
- B.Bubble sort(correct answer)
- C.Merge sort
- D.Heap sort
Large values “bubble” to the end on each pass.
Q10. Merge sort uses which design technique?
- A.Greedy
- B.Divide and conquer(correct answer)
- C.Dynamic programming
- D.Backtracking
It divides the array, sorts each half, then combines them.
Q11. How much extra space does standard merge sort on an array need?
- A.O(1)
- B.O(log n)
- C.O(n)(correct answer)
- D.O(n²)
Merging needs a temporary array as large as the input.
Q12. Counting sort is efficient when:
- A.The range of key values is small(correct answer)
- B.The data is in a linked list
- C.Keys are floating-point numbers
- D.The array is nearly sorted
It runs in O(n + k), where k is the range of keys.
Q13. How many swaps does selection sort make in the worst case for n elements?
- A.O(1)
- B.O(n)(correct answer)
- C.O(n log n)
- D.O(n²)
At most one swap per pass, so at most n - 1 swaps.
Q14. What is the worst-case time complexity of heap sort?
- A.O(n)
- B.O(n log n)(correct answer)
- C.O(n²)
- D.O(log n)
Building the heap is O(n), and each of n extractions costs O(log n).
Q15. What is the average time to look up a key in a well-designed hash table?
- A.O(1)(correct answer)
- B.O(log n)
- C.O(n)
- D.O(n log n)
The hash function points almost directly to the right bucket.
Q16. Binary search on a sorted array of 1,000,000 elements needs roughly how many steps in the worst case?
- A.20(correct answer)
- B.1,000
- C.500,000
- D.1,000,000
log2(1,000,000) is about 20.