Data Structures Sorting and Searching Algorithms

Question 1

What is the average time complexity of quicksort?

Accepted Answer

O(n log n)

Answer

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?

Accepted Answer

Merge sort

Answer

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?

Accepted Answer

Stable sorts preserve the relative order of equal elements; unstable sorts may not

Answer

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?

Accepted Answer

O(log n)

Answer

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?

Accepted Answer

Insertion sort

Answer

Insertion sort performs O(n) comparisons on nearly sorted data because elements are already close to their final positions, requiring minimal shifting.

Data Structures Practice Test

Data Structures Practice Test

Data Structures Sorting and Searching Algorithms