Divide and Conquer Strategy and Worst-Case Linear Time Selection Algorithm

Divide and Conquer is an algorithm design paradigm that solves a problem by recursively breaking it into smaller sub-problems, solving each sub-problem independently, and then combining their solutions to get the final answer.

---

Divide and Conquer Strategy

The strategy works in three steps:

• Divide: Break the original problem into smaller sub-problems of the same type.
• Conquer: Solve each sub-problem recursively. If the sub-problem is small enough, solve it directly (base case).
• Combine: Merge the solutions of sub-problems to form the solution of the original problem.

General Recurrence:

$$T(n) = aT\left(\frac{n}{b}\right) + f(n)$$

Where $a$ = number of sub-problems, $n/b$ = size of each sub-problem, $f(n)$ = cost of dividing and combining.

Examples: Merge Sort, Quick Sort, Binary Search, Strassen's Matrix Multiplication.

---

Worst-Case Linear Time Selection Algorithm (Median of Medians)

The Worst-Case Linear Time Selection algorithm (also called SELECT or Median of Medians) finds the i$-th smallest element in an unsorted array in $O(n) time in the worst case.

Unlike Randomized Select (which has $O(n^2)$ worst case), this algorithm guarantees linear time by choosing a good pivot.

Steps of the Algorithm:

• Step A: Divide the $n$ elements into groups of 5 (last group may have fewer elements). This gives $\lceil n/5 \rceil$ groups.

• Step B: Find the median of each group by sorting each group (takes constant time since group size is 5).

• Step C: Recursively find the median of these medians using SELECT. Call this pivot $x$.

• Step D: Partition the array around pivot $x$. Let $x$ be at position $k$ after partitioning.

• Step E:

  • If $i = k$, return $x$.
  • If $i < k$, recursively select the $i$-th smallest in the left partition.
  • If $i > k$, recursively select the $(i - k)$-th smallest in the right partition.

---

Complexity Analysis

Key Insight: The median of medians guarantees that at least 30% of elements are smaller and at least 30% of elements are larger than the pivot. So the worst-case recursive call is on at most 70% of elements (i.e., $7n/10$).

Counting elements guaranteed to be eliminated:

• At least half of the $\lceil n/5 \rceil$ medians are $\geq x$, i.e., at least $\lceil n/10 \rceil$ groups.
• Each such group contributes at least 3 elements $\geq x$.
• So at least $3 \times \lceil n/10 \rceil \approx 3n/10$ elements are $\geq x$.
• Similarly, $3n/10$ elements are $\leq x$.
• Worst case: recursive call on at most $n - 3n/10 = 7n/10$ elements.

Recurrence Relation:

$$T(n) = T\left(\frac{n}{5}\right) + T\left(\frac{7n}{10}\right) + O(n)$$

Where:

• $T(n/5)$ = finding median of medians recursively
• $T(7n/10)$ = recursive selection in the larger partition
• $O(n)$ = partitioning and grouping

Solving the Recurrence:

Assume $T(n) \leq cn$ for some constant $c$:

$$T(n) \leq c\frac{n}{5} + c\frac{7n}{10} + an$$

$$T(n) \leq cn\left(\frac{1}{5} + \frac{7}{10}\right) + an = cn\left(\frac{9}{10}\right) + an$$

$$T(n) \leq \frac{9cn}{10} + an \leq cn$$

This holds when $an \leq cn/10$, i.e., $c \geq 10a$.

Therefore:

$$\boxed{T(n) = O(n)}$$

---

Conclusion

The Divide and Conquer strategy is a powerful paradigm for designing efficient algorithms. The Median of Medians algorithm cleverly applies this strategy to achieve guaranteed $O(n)$ worst-case time for selection, improving over Quick Select's $O(n^2)$ worst case by ensuring a balanced partition through careful pivot selection.