What is the worst-case time complexity of the deterministic selection algorithm (Median-of-Medians with groups of 5) to find the k-th smallest element?
By dividing into groups of 5 and finding the median of medians, the recurrence T(n) <= T(n/5) + T(7n/10) + O(n) yields T(n) = O(n) worst-case time.
In the deterministic linear-time selection algorithm (BFPRT), why are groups of size 5 (or 7) chosen instead of size 3?
For group size 3, 1/3 + 2/3 = 1, giving T(n) = T(n/3) + T(2n/3) + O(n) = O(n log n). For group size 5, 1/5 + 7/10 = 9/10 < 1, yielding O(n).
In the Divide and Conquer algorithm for finding the closest pair of points in 2D space, how many points in the strip around the dividing line must be checked for each point?
Geometric constraints (packing inside a $\delta x 2 \delta rectangle) guarantee$ that for each point in the strip sorted by y-coordinate, at most 7 following points need to be inspected.
What is the optimal time complexity to find the closest pair of points among n 2D points using Divide and Conquer?
By pre-sorting points by x and y coordinates, dividing the plane by a vertical line, solving subproblems, and scanning the strip in O(n) time, T(n) = 2T(n/2) + O(n) = O(n log n).
How many multiplications are required to compute $x^n$ using Divide and Conquer fast exponentiation?
Fast exponentiation uses x^$n = (x^{n/2})^2$ for even n, and x * $x^{n-1}$ for odd n. Recurrence T(n) = T(n/2) + O(1) gives $\Theta(log n) multiplications$.