Which algorithm uses Divide and Conquer and has an average-case time complexity of O(N log N)?

Options

  • A. Quick Sort
  • B. Bubble Sort
  • C. Linear Search
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. Quick Sort

Detailed Explanation

Quick Sort is a Divide and Conquer sorting algorithm. It selects a pivot, partitions the array around that pivot, and recursively sorts the resulting subarrays. Its average-case time complexity is O(N log N), although its worst-case complexity can become O(N2) when partitions are highly unbalanced. Pivot-selection strategies such as randomized or median-based selection can help reduce the likelihood of poor partitions.