Question 21
What is the worst-case time complexity of Binary Search?
Binary search repeatedly divides the sorted search space in half, resulting in a logarithmic worst-case running time of O(log n).
What is the worst-case time complexity of Binary Search?
Binary search repeatedly divides the sorted search space in half, resulting in a logarithmic worst-case running time of O(log n).
Which condition must be met before executing Binary Search on an array?
Binary search eliminates half of the remaining search interval after each comparison, which is possible only when the array is sorted. For arrays, direct indexing provides O(1) access to the middle element.
Worst-case time complexity of Linear Search is -
In Linear Search, if the target is at the last position or absent, all n elements are inspected sequentially, taking O(n) time.
Which sorting algorithm works on the Divide and Conquer strategy?
Quick Sort selects a pivot, partitions elements into smaller and larger sub-arrays (Divide), and recursively sorts them (Conquer).
With a first-element or last-element pivot strategy, which input arrangement can cause Quick Sort to reach its worst-case time complexity?
If the pivot is repeatedly the smallest or largest element, partitions have sizes 0 and n-1. This creates recursion depth O(n) and total work O(n²). Already sorted or reverse-sorted input causes this for common first/last-element pivot rules, but not for every pivot strategy.