Data Structures Sorting and Searching Algorithms 1 — Questions and Answers
Question 1: What is the average time complexity of quicksort?
- O(n)
- O(n log n) (Correct answer)
- O(n²)
- O(log n)
Correct answer: O(n log n)
Quicksort's average case is O(n log n) because the partition step is O(n) and on average produces balanced halves, giving O(log n) levels of recursion.
Question 2: Which sorting algorithm has the best worst-case time complexity?
- Quicksort
- Insertion sort
- Merge sort (Correct answer)
- Bubble sort
Correct answer: Merge sort
Merge sort guarantees O(n log n) in all cases — best, average, and worst — because it always splits evenly and merges linearly.
Question 3: What is the key difference between stable and unstable sorting algorithms?
- Stable sorts are always faster
- Stable sorts preserve the relative order of equal elements; unstable sorts may not (Correct answer)
- Stable sorts require O(1) extra space
- Unstable sorts cannot sort strings
Correct answer: Stable sorts preserve the relative order of equal elements; unstable sorts may not
A stable sort ensures that two records with equal keys appear in the same relative order in the sorted output as in the input.
Question 4: What is the time complexity of binary search on a sorted array?
- O(n)
- O(n log n)
- O(log n) (Correct answer)
- O(1)
Correct answer: O(log n)
Binary search halves the search space at each step, requiring at most log₂ n comparisons to find or rule out a target.
Question 5: Which sorting algorithm is most efficient for nearly sorted data?
- Merge sort
- Heapsort
- Insertion sort (Correct answer)
- Selection sort
Correct answer: Insertion sort
Insertion sort performs O(n) comparisons on nearly sorted data because elements are already close to their final positions, requiring minimal shifting.
Question 6: What is the space complexity of merge sort?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n log n)
Correct answer: O(n)
Merge sort requires O(n) auxiliary space for the temporary arrays used during the merge step.
Data Structures Sorting and Searching Algorithms 1
What is the average time complexity of quicksort?