Which recurrence relation correctly describes Binary Search on a sorted array of n elements?
Binary Search compares the middle element ($\Theta(1)$) and recurses on one half of size n/2. By Master Theorem Case 2, T(n) = $\Theta(log n)$.
Asymptotically, how many comparisons does Quick Sort perform on average for n distinct elements?
For randomized Quick Sort (and equivalently the average over all pivot orders), the expected number of comparisons is 2(n+1)$H_{n}$ - 4n = $\Theta(n log n), asymptotically about 2n ln n \approx 1.386 n log_2 n$.
What is the time complexity of finding the maximum subarray sum using a Divide and Conquer approach?
Divide & Conquer splits array into 2 halves, solves subproblems, and calculates max crossing sum in O(n) time. T(n) = 2T(n/2) + O(n) = O(n log n). (Note: Kadane's algorithm does it in O(n)).
What is the time complexity of counting inversions in an array of size n using a modified Merge Sort?
During the merge step of Merge Sort, if an element from the right subarray is smaller than an element from the left subarray, it contributes (mid - i + 1) inversions. Total time remains O(n log n).
What is the maximum number of inversions possible in an array of size n?
A reverse-sorted array contains the maximum number of inversions. Every pair (i, j) with i < j is inverted. Total pairs = n(n-1)/2.