Divide & Conquer

CS F364 — Design & Analysis of Algorithms | Summer 2026

Merge sort variants, missing integer, MST, convex polygon, matrix search

← Practice

NoteProblem 1

Merge sort with insertion sort. Merge sort runs in \Theta(n\log n) worst-case time, while insertion sort runs in \Theta(n^2). But insertion sort is faster for small n. Consider a modified merge sort where n/k sublists of length k are sorted using insertion sort, then merged using the standard merging mechanism.

  1. What is the worst-case time to sort the n/k sublists (each of length k)?

  2. Show that the sublists can be merged in \Theta(n\log(n/k)) worst-case time.

  3. What is the largest asymptotic (\Theta) value of k (as a function of n) for which the modified algorithm has the same asymptotic running time as standard merge sort?

(i) Sorting one sublist of length k with insertion sort takes \Theta(k^2) in the worst case. There are n/k such sublists, so the total is: \frac{n}{k} \cdot \Theta(k^2) = \Theta(nk). (ii) Merge n/k sorted lists using a binary merge tree of height \log_2(n/k). At each level, all n elements are compared and merged, contributing \Theta(n) per level. Hence total merge time: \Theta\!\left(n\log\frac{n}{k}\right). (iii) Total time of modified sort: \Theta\!\left(nk + n\log\frac{n}{k}\right). For this to match \Theta(n\log n), we need nk = O(n\log n), i.e., k = O(\log n). The largest asymptotic value is k = \Theta(\log n).

NoteProblem 2

Missing integer. Given an unsorted array of all integers in the range 0 to n = 2^k - 1 except for one missing integer (every non-missing integer appears exactly once), design an O(n) divide-and-conquer algorithm to find the missing integer. Argue informally that your algorithm is correct and analyze its running time.

Algorithm \text{MissingInteger}(A, [\ell, r]):

  1. If \ell = r, return \ell (the single candidate).
  2. Let m = \lfloor (\ell+r)/2 \rfloor.
  3. Count how many elements in A are \le m. Call this c.
  4. If c < m - \ell + 1, the missing integer lies in [\ell, m]; recurse on the elements \le m.
  5. Otherwise, the missing integer lies in [m+1, r]; recurse on the elements > m.

Analysis: Each recursive call partitions the array in O(|A|) time (counting and partitioning). Since the range halves each step, the total is O(n + n/2 + n/4 + \dots) = O(n).

Correctness: In a complete set of integers 0 to 2^k-1, exactly m-\ell+1 numbers would lie in [\ell, m]. If fewer are present, the missing number must be in the left half; otherwise it is in the right half.

NoteProblem 3

D&C for MST — correct or not? Consider this divide-and-conquer algorithm for MST: Given an undirected weighted graph G(V,E), partition V into V_1 and V_2 such that |V_1| and |V_2| differ by at most 1. Let E_1 be edges incident only on V_1, E_2 edges incident only on V_2. Recursively solve MST on G_1(V_1,E_1) and G_2(V_2,E_2). Finally, select the minimum-weight edge crossing the cut (V_1, V_2) and use it to unite the two MSTs. Either prove this algorithm is correct or disprove it with a counterexample.

The algorithm is incorrect.

Counterexample: Graph G with vertices V = \{v_1, v_2, v_3, v_4\} and edges: e(v_1,v_2)=4,\; e(v_2,v_3)=2,\; e(v_3,v_4)=5,\; e(v_4,v_1)=1. Partition V_1 = \{v_1, v_2\}, V_2 = \{v_3, v_4\}. - MST of G_1: edge (v_1,v_2) of weight 4. - MST of G_2: edge (v_3,v_4) of weight 5. - Minimum crossing edge: (v_4,v_1) of weight 1.

Total weight = 4 + 5 + 1 = 10.

But the actual MST cost is 7: edges (v_4,v_1,1), (v_2,v_3,2), (v_1,v_2,4).

The failure occurs because the minimum crossing edge is not necessarily the best way to connect two MSTs — the cut-and-cycle properties of MST require considering all edges, not just a recursive decomposition.

NoteProblem 4

Convex polygon vertices. Let E be an unsorted set of n segments that are the edges of a convex polygon. Give an O(n\log n) algorithm that produces a list of all vertices of the polygon sorted in counter-clockwise order. Describe each step in plain English and analyze the running time.

Algorithm:

  1. Pick an arbitrary segment s_1 = \overline{pq}. Let p be one endpoint of s_1.
  2. Find the other segment s_2 that shares endpoint p (scan E).
  3. Walk along s_1 to the other endpoint a. Check the orientation of the two segments incident at p to determine the polygon’s interior.
  4. For each edge endpoint, compute its polar angle with respect to a fixed reference point (e.g., the polygon’s centroid).
  5. Sort all vertices by angle — O(n\log n).
  6. Output in sorted order, skipping duplicate vertex entries.

Analysis: Steps 1–3 and 6 require O(n) time. Step 5 (sorting) takes O(n\log n). Hence total O(n\log n).

NoteProblem 5

nth smallest of two sorted arrays. Let A[1..n] and B[1..n] be two sorted arrays of integers (increasing order). Give a divide-and-conquer algorithm that finds the nth smallest element of the combined 2n elements in O(\log n) time. All 2n elements are distinct.

Algorithm \text{Select}(A, B, n):

  1. If n = 1, return \min(A[1], B[1]).
  2. Compare A[\lfloor n/2\rfloor] and B[\lfloor n/2\rfloor].
  3. If A[\lfloor n/2\rfloor] > B[\lfloor n/2\rfloor], then the nth smallest is the \lfloor n/2\rfloorth smallest of the union of A[1..\lfloor n/2\rfloor] and B[\lceil n/2\rceil+1..n] — discard the larger half of B and the smaller half of A.
  4. Otherwise, discard symmetrically.
  5. Recurse.

Analysis: Each step discards roughly half the elements and does O(1) work. Recurrence T(n) = T(n/2) + O(1) = O(\log n).

Correctness: Since B[\lfloor n/2\rfloor] is smaller than both A[\lfloor n/2\rfloor] and all n - \lfloor n/2\rfloor elements after it, it cannot be among the n smallest. The discarded elements are safely eliminated.

NoteProblem 6

Frequent-value detection. Given an arbitrary array A[1..n], determine in O(n) time whether any value appears more than n/4 times. You may not use hashing, radix sort, or any method that depends on precise input values (as opposed to their order).

If an element x appears more than n/4 times, it must occupy at least one of the \lfloor n/4\rfloor, \lfloor 2n/4\rfloor, or \lfloor 3n/4\rfloor positions in sorted order.

Algorithm:

  1. Find the \lfloor n/4\rfloorth, \lfloor 2n/4\rfloorth, and \lfloor 3n/4\rfloorth order statistics using deterministic SELECT (linear time each). Call them x_1, x_2, x_3.
  2. For each x_i, scan the array and count how many times x_i appears.
  3. If any count > n/4, output true; otherwise false.

Analysis: Three SELECT calls plus three scans = 3\cdot O(n) + 3\cdot O(n) = O(n) total.

Correctness: A majority-like element with frequency > n/4 must cross at least one quartile boundary. Any such element will be picked as one of x_1, x_2, x_3 and detected in the scan.

NoteProblem 7

Search in a sorted matrix. The elements of an n\times n array A are arranged in ascending rows and columns: A[i][j] < A[i][j'] whenever j < j', and A[i][j] < A[i'][j] whenever i < i'. Give the most efficient algorithm to determine if A contains a target element x, and compute the best upper bound on its asymptotic worst-case running time.

Algorithm: Start at the top-right corner A[1][n].

  • If A[1][n] > x, eliminate the last column (all elements below are larger) — move left.
  • If A[1][n] < x, eliminate the first row (all elements to the left are smaller) — move down.
  • If equal, return true.

Repeat until the element is found or we exit the matrix.

Analysis: Each step eliminates either one row or one column. There are n rows and n columns, so at most 2n steps. Each step is O(1). Worst-case: O(n).

This is optimal because a decision-tree lower bound requires \Omega(n) comparisons in the worst case (the element could be in any of n possible anti-diagonal positions).