Unit 1: Analysis of Algorithms and Divide-and-Conquer

1. Foundations of Algorithm Analysis and Theoretical Frameworks

Algorithm analysis is the branch of computer science dedicated to estimating the resource utilization—primarily execution time and memory space—of an algorithm as a mathematical function of its input size $n$. By characterizing resource growth independently of ephemeral physical hardware, compiler optimizations, or specific programming language runtimes, algorithm analysis establishes rigorous theoretical guarantees for scalability and algorithmic efficiency.

1.1 The Random Access Machine (RAM) Model of Computation

Theoretical algorithm analysis relies on an idealized computational abstraction termed the Random Access Machine (RAM) model:

• Sequential Execution: Instructions execute sequentially one after another with no concurrent or parallel hardware multiprocessing unless explicitly modeled.
• Uniform Memory Access: Accessing any memory cell takes constant time $\mathcal{O}(1)$, regardless of physical hardware phenomena such as CPU L1/L2/L3 cache hierarchies, virtual memory paging, or TLB misses.
• Unit-Cost Operations: Elementary operations—arithmetic calculations (addition, subtraction, multiplication, integer division), comparisons ($<, \le, ==, \ge, >$), logical operations (AND, OR, NOT), bitwise shifts, variable assignments, and pointer dereferences—are executed in constant time $\mathcal{O}(1)$.
• Bounded Word Size: Each memory word consists of $c \lg n$ bits (typically 32 or 64 bits), ensuring that basic integers representing array indices and input sizes can be stored in a single machine word and manipulated in $\mathcal{O}(1)$ time without requiring multi-precision arbitrary-length arithmetic.

1.2 Input Size and Problem Scaling

The input size $n$ characterizes the magnitude of the problem instance:

• For linear sequences, arrays, and lists, $n$ denotes the total count of elements.
• For graphs $G = (V, E)$, input complexity is bi-variate, parameterized by both the number of vertices $|V|$ and the number of edges $|E|$.
• For cryptographic and number-theoretic algorithms (e.g., primality testing, RSA factorization), input size is defined not by the numeric value $N$ itself, but by the number of bits $\beta = \lceil \log_2(N + 1) \rceil$ required to represent $N$ in binary. An algorithm running in $\mathcal{O}(N)$ arithmetic operations is therefore pseudo-polynomial, as its complexity is exponential $\mathcal{O}(2^\beta)$ relative to the true binary input length $\beta$.

1.3 Asymptotic Notations and Formal Definitions

Asymptotic analysis examines the growth rate of an algorithm's resource function $T(n)$ as $n \to \infty$, disregarding machine-dependent constant multipliers and asymptotically insignificant lower-order terms.

CODECopy Code
      Running Time T(n)
         ▲
         │                 c2 * g(n)  [Upper Bound]
         │              ..·'
         │           .·'    f(n)      [Exact Bound]
         │        .·'   ..·'
         │     .·'   .·'
         │  .·'   .·'      c1 * g(n)  [Lower Bound]
         │ '   .·'
         │  .·'
         │.·'
         └─────────────┼─────────────────────────► Input Size n
                      n0

1. Big-O Notation ($\mathcal{O}$ - Asymptotic Upper Bound):

   • Definition: $f(n) = \mathcal{O}(g(n))$ if there exist positive constants $c > 0$ and $n_0 \ge 1$ such that:
     $0 \le f(n) \le c \cdot g(n) \quad \text{for all } n \ge n_0$
   • Significance: Represents the maximum upper envelope of growth. Guarantees that the algorithm will not take longer than $c \cdot g(n)$ for sufficiently large inputs.

2. Big-Omega Notation ($\Omega$ - Asymptotic Lower Bound):

   • Definition: $f(n) = \Omega(g(n))$ if there exist positive constants $c > 0$ and $n_0 \ge 1$ such that:
     $0 \le c \cdot g(n) \le f(n) \quad \text{for all } n \ge n_0$
   • Significance: Represents the minimum baseline resource requirement. Asserts that the algorithm requires at least $c \cdot g(n)$ operations on large inputs.

3. Big-Theta Notation ($\Theta$ - Asymptotically Tight Bound):

   • Definition: $f(n) = \Theta(g(n))$ if and only if $f(n) = \mathcal{O}(g(n))$ and $f(n) = \Omega(g(n))$. Formally, there exist positive constants $c_1, c_2 > 0$ and $n_0 \ge 1$ such that:
     $0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \quad \text{for all } n \ge n_0$
   • Significance: Sandwiches the running time within a constant-factor envelope. $g(n)$ provides an asymptotically exact characterization.

4. Little-o and Little-omega Notations ($o$ and $\omega$):

   • $f(n) = o(g(n))$ represents an upper bound that is not asymptotically tight:
     $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$
   • $f(n) = \omega(g(n))$ represents a lower bound that is not asymptotically tight:
     $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

1.4 Cases of Analysis: Worst-Case, Best-Case, and Average-Case

• Worst-Case Complexity ($T_{\text{worst}}(n)$): The maximum execution cost over all possible input instances of size $n$:
  $T_{\text{worst}}(n) = \max_{I \in \mathcal{D}_n} \text{Cost}(I)$
  Serves as the primary metric in enterprise and critical systems because it provides an unconditional upper guarantee.
• Best-Case Complexity ($T_{\text{best}}(n)$): The minimum execution cost across all inputs of size $n$:
  $T_{\text{best}}(n) = \min_{I \in \mathcal{D}_n} \text{Cost}(I)$
  Identifies optimal inputs (e.g., an already sorted array for Insertion Sort).
• Average-Case Complexity ($T_{\text{avg}}(n)$): The probabilistic expected value of cost across all possible input permutations under an assumed probability distribution $P(I)$:
  $T_{\text{avg}}(n) = \sum_{I \in \mathcal{D}_n} P(I) \cdot \text{Cost}(I)$
  Often assumes a uniform distribution where each permutation is equally likely ($P(I) = 1 / n!$).

2. Iterative and Incremental Sorting Analysis: Insertion Sort

Insertion Sort is an archetypal incremental comparison-based sorting algorithm. It constructs the final sorted array one element at a time by repeatedly taking the next unsorted element and inserting it into its correct position within the already sorted prefix.

2.1 Algorithmic Mechanics and Pseudocode

CODECopy Code
INSERTION-SORT(A, n)
1  for j = 2 to n
2      key = A[j]
3      // Insert A[j] into the sorted sequence A[1 .. j-1]
4      i = j - 1
5      while i > 0 and A[i] > key
6          A[i + 1] = A[i]
7          i = i - 1
8      A[i + 1] = key

2.2 Loop Invariant and Correctness Proof

The correctness of Insertion Sort is established using a formal Loop Invariant:

• Invariant Statement: At the start of each iteration of the outer for loop (line 1), the subarray $A[1 \dots j-1]$ consists of the elements originally in $A[1 \dots j-1]$, but arranged in sorted order.
• Initialization: Prior to the first iteration ($j = 2$), the subarray is $A[1 \dots 1]$, consisting of a single element. A single-element subarray is trivially sorted. The invariant holds.
• Maintenance: During iteration $j$, lines 4–7 shift elements $A[j-1], A[j-2], \dots$ that are strictly greater than key one position to the right until the correct insertion slot is located. Line 8 deposits key into that position. The resulting subarray $A[1 \dots j]$ now contains the original elements in sorted order. Incrementing $j$ for the next loop iteration preserves the invariant.
• Termination: The loop terminates when $j = n + 1$. Substituting $j = n + 1$ into the invariant yields: the subarray $A[1 \dots n]$ consists of the elements originally in $A[1 \dots n]$, arranged in sorted order. Hence, the entire array is sorted.

2.3 Mathematical Complexity Analysis

Let $t_j$ represent the number of times the while loop condition (line 5) is evaluated for a given index $j$:
$T(n) = c_1 n + c_2 (n - 1) + c_4 (n - 1) + c_5 \sum_{j=2}^n t_j + c_6 \sum_{j=2}^n (t_j - 1) + c_7 \sum_{j=2}^n (t_j - 1) + c_8 (n - 1)$

• Best-Case Analysis (Already Sorted Array):
  • If the array is already sorted in non-decreasing order, $A[i] \le \text{key}$ on the very first comparison of line 5.
  • Thus, $t_j = 1$ for all $j \in \{2, \dots, n\}$.
  • The sums $\sum_{j=2}^n t_j = n - 1$ and $\sum_{j=2}^n (t_j - 1) = 0$.
  • Result: $T(n) = a n + b = \Theta(n)$ (linear time).
• Worst-Case Analysis (Reverse Sorted Array):
  • If the array is sorted in strictly descending order, every element in $A[1 \dots j-1]$ is greater than key.
  • The while loop must shift all $j-1$ elements: $t_j = j$.
  • The sum evaluates to:
    $\sum_{j=2}^n j = \frac{n(n + 1)}{2} - 1 = \Theta(n^2)$
  • Result: $T(n) = c n^2 + d n + e = \Theta(n^2)$ (quadratic time).
• Average-Case Analysis:
  • Assuming a uniform distribution of distinct keys, on average half of the elements in $A[1 \dots j-1]$ are greater than key: $t_j \approx j/2$.
  • The sum $\sum_{j=2}^n (j/2) \approx \frac{1}{2} \cdot \frac{n^2}{2} = \Theta(n^2)$.
• Space Complexity:
  • Insertion Sort sorts strictly in-place. It requires only a constant number of auxiliary scalar variables (key, i, j), yielding $\mathcal{O}(1)$ auxiliary space complexity.

3. The Divide-and-Conquer Paradigm and Merge Sort

The Divide-and-Conquer algorithmic paradigm structures problem resolution into three recursive phases:

1. Divide: Partition the problem instance into two or more disjoint, smaller subproblems of the same type.
2. Conquer: Solve the subproblems recursively. If the subproblem size is sufficiently small (the base case), solve it directly using a primitive base routine.
3. Combine: Merge the solutions of the subproblems into a unified solution for the original problem instance.

3.1 Merge Sort Mechanics and Recurrence Formulation

Merge Sort divides an array of size $n$ into two equal halves of size $n/2$, recursively sorts each half, and combines the two sorted subarrays using a linear-time merging routine.

CODECopy Code
MERGE-SORT(A, p, r)
1  if p < r
2      q = floor((p + r) / 2)       // Divide: O(1)
3      MERGE-SORT(A, p, q)          // Conquer: T(n/2)
4      MERGE-SORT(A, q + 1, r)      // Conquer: T(n/2)
5      MERGE(A, p, q, r)            // Combine: Theta(n)

The merging procedure MERGE(A, p, q, r) allocates two auxiliary buffers $L$ and $R$ to copy the left and right sorted segments, uses two pointers to compare their front elements, and writes the smaller element back into array $A$. Because each comparison places at least one element into its final sorted destination, MERGE executes in exactly $\Theta(n)$ time, where $n = r - p + 1$.

The overall running time is characterized by the recurrence relation:
$T(n) = \begin{cases} \Theta(1) & \text{if } n = 1 \\ 2 T(n/2) + \Theta(n) & \text{if } n > 1 \end{cases}$

3.2 Complexity and Stability Properties of Merge Sort

• Time Complexity: As solved via the Master Theorem or Recursion Tree, $T(n) = \Theta(n \lg n)$ across all cases (best-case, average-case, and worst-case). Unlike Quick Sort, Merge Sort guarantees $\mathcal{O}(n \lg n)$ worst-case time unconditionally.
• Space Complexity: Standard array-based Merge Sort requires allocating auxiliary arrays of size $n/2$ during merges. The maximum auxiliary space allocated at any point in the call tree is $\Theta(n)$. Thus, standard Merge Sort is not an in-place sort ($\mathcal{O}(n)$ auxiliary space).
• Stability: A sorting algorithm is stable if elements with identical comparison keys retain their relative original input order. Merge Sort is inherently stable provided the merge step resolves equal keys by selecting from the left buffer first (L[i] <= R[j]).

4. Analytical Methods for Solving Recurrences

Divide-and-conquer recurrences take the general form $T(n) = a T(n/b) + f(n)$. Three primary mathematical techniques exist to solve such recurrences:

4.1 The Substitution Method

The Substitution Method employs a two-step process: (1) guess the form of the mathematical bound, and (2) apply mathematical induction to determine the constants and prove correctness.

Example: Solve $T(n) = 2 T(\lfloor n/2 \rfloor) + n$.

• Inductive Hypothesis: Guess $T(n) \le c n \lg n$ for some constant $c > 0$.
• Inductive Step: Assume the bound holds for all integers $m < n$, specifically for $m = \lfloor n/2 \rfloor$:
  $T(\lfloor n/2 \rfloor) \le c \lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor)$
• Substituting into the recurrence:
  $T(n) \le 2 \left(c \lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor)\right) + n \le 2 \left(c \frac{n}{2} \lg\frac{n}{2}\right) + n = c n (\lg n - \lg 2) + n = c n \lg n - c n + n$
• To satisfy $T(n) \le c n \lg n$, we must ensure:
  $c n \lg n - c n + n \le c n \lg n \iff -c n + n \le 0 \iff c \ge 1$
• Choosing $c \ge 1$ completes the inductive step. Base cases $n = 2, 3$ confirm the hypothesis, proving $T(n) = \mathcal{O}(n \lg n)$.

4.2 The Recursion Tree Method

The Recursion Tree method models the recursive unfolding of the algorithm as a rooted tree, calculating the cost incurred at each level and summing across all levels:

CODECopy Code
Level 0:                         f(n)                          Cost = f(n)
                               /      \
Level 1:                 f(n/b)        f(n/b)                  Cost = a * f(n/b)
                        /      \      /      \
Level 2:             f(n/b^2) ........... f(n/b^2)             Cost = a^2 * f(n/b^2)
                       ...                  ...
Level log_b(n):        T(1) T(1) T(1) ... T(1) T(1)           Cost = a^(log_b n) * T(1)
                                                                    = n^(log_b a) * Theta(1)

1. Tree Height: At depth $i$, the subproblem size is $n / b^i$. The subproblem reaches the base case $n / b^i = 1$ at depth $i = \log_b n$. The tree depth is $\log_b n$.
2. Leaf Node Count: The branching factor is $a$. At depth $h = \log_b n$, the number of leaves is:
   $\text{Leaves} = a^{\log_b n} = n^{\log_b a}$
3. Total Work: Total cost is the sum of the non-recursive work $f(n/b^i)$ at all internal levels plus the cost of the leaves:
   $T(n) = \sum_{i=0}^{\log_b n - 1} a^i f(n / b^i) + \Theta(n^{\log_b a})$

4.3 The Master Method

The Master Theorem provides a cookbook solution for recurrences of the standard form:
$T(n) = a T(n/b) + f(n)$
where $a \ge 1$ is the number of subproblems, $b > 1$ is the subproblem reduction factor, and $f(n)$ is an asymptotically positive function representing division and recombination cost.

The behavior is determined by comparing $f(n)$ against the watershed function $n^{\log_b a}$:

Non-Applicability and Limitations of the Master Theorem

The Master Theorem cannot be applied if:

• $a$ is not a constant (e.g., $T(n) = n T(n/2) + n$).
• $b$ is non-constant or represents subtraction rather than division (e.g., $T(n) = T(n-1) + n$).
• The gap between $f(n)$ and $n^{\log_b a}$ is not polynomial. For example, in $T(n) = 2T(n/2) + n / \lg n$, $n^{\log_2 2} = n$. The ratio $f(n) / n^{\log_b a} = 1 / \lg n$ is smaller than 1, but not by a polynomial factor $n^\epsilon$. Hence, Case 1 does not apply, and the recurrence must be solved using recursion trees or substitution ($T(n) = \Theta(n \lg \lg n)$).

5. Sub-Cubic Matrix Multiplication: Strassen's Algorithm

Multiplying two $n \times n$ dense matrices $A$ and $B$ to produce $C = A \times B$ is a fundamental computational primitive:
$C_{ij} = \sum_{k=1}^n A_{ik} B_{kj}$
Standard triple-nested loop multiplication performs $n$ multiplications and $n-1$ additions for each of the $n^2$ entries, yielding $\Theta(n^3)$ operations.

5.1 Naive Divide-and-Conquer Matrix Multiplication

Partitioning $A$, $B$, and $C$ into four $(n/2) \times (n/2)$ submatrices:
$\begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{pmatrix} = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix}$
yields four submatrix equations:

• $C_{11} = A_{11} B_{11} + A_{12} B_{21}$
• $C_{12} = A_{11} B_{12} + A_{12} B_{22}$
• $C_{21} = A_{21} B_{11} + A_{22} B_{21}$
• $C_{22} = A_{21} B_{12} + A_{22} B_{22}$

This naive divide-and-conquer formulation requires:

• $a = 8$ recursive matrix multiplications of size $n/2$.
• 4 matrix additions of size $n/2$, costing $\Theta(n^2)$ time.
  Recurrence: $T(n) = 8 T(n/2) + \Theta(n^2)$.
  By Master Theorem Case 1 ($n^{\log_2 8} = n^3$): $T(n) = \Theta(n^3)$. This achieves zero asymptotic improvement over the naive iterative approach.

5.2 Strassen's Algebraic Insight

In 1969, Volker Strassen published a breakthrough method that reduced the number of recursive multiplications from 8 to 7, at the cost of 18 matrix additions/subtractions:

1. Step 1: Divide matrices $A$ and $B$ into submatrices of size $(n/2) \times (n/2)$ in $\Theta(1)$ index time.
2. Step 2: Create 10 additive submatrices $S_1, S_2, \dots, S_{10}$ using matrix additions and subtractions:
   • $S_1 = B_{12} - B_{22}$
   • $S_2 = A_{11} + A_{12}$
   • $S_3 = A_{21} + A_{22}$
   • $S_4 = B_{21} - B_{11}$
   • $S_5 = A_{11} + A_{22}$
   • $S_6 = B_{11} + B_{22}$
   • $S_7 = A_{12} - A_{22}$
   • $S_8 = B_{21} + B_{22}$
   • $S_9 = A_{11} - A_{21}$
   • $S_{10} = B_{11} + B_{12}$
3. Step 3: Recursively compute 7 matrix products $P_1, P_2, \dots, P_7$:
   • $P_1 = A_{11} \cdot S_1 = A_{11} B_{12} - A_{11} B_{22}$
   • $P_2 = S_2 \cdot B_{22} = A_{11} B_{22} + A_{12} B_{22}$
   • $P_3 = S_3 \cdot B_{11} = A_{21} B_{11} + A_{22} B_{11}$
   • $P_4 = A_{22} \cdot S_4 = A_{22} B_{21} - A_{22} B_{11}$
   • $P_5 = S_5 \cdot S_6 = (A_{11} + A_{22})(B_{11} + B_{22})$
   • $P_6 = S_7 \cdot S_8 = (A_{12} - A_{22})(B_{21} + B_{22})$
   • $P_7 = S_9 \cdot S_{10} = (A_{11} - A_{21})(B_{11} + B_{12})$
4. Step 4: Combine the products to construct the quadrants of $C$:
   • $C_{11} = P_5 + P_4 - P_2 + P_6$
   • $C_{12} = P_1 + P_2$
   • $C_{21} = P_3 + P_4$
   • $C_{22} = P_5 + P_1 - P_3 - P_7$

5.3 Complexity Analysis and Practical Engineering Trade-offs

• Recurrence Relation:
  $T(n) = 7 T(n/2) + \Theta(n^2)$
• Solving via Master Theorem:
  • $a = 7, b = 2 \implies n^{\log_b a} = n^{\log_2 7} \approx n^{2.807}$.
  • $f(n) = \Theta(n^2)$.
  • Since $2 < 2.807$, $f(n) = \mathcal{O}(n^{\log_2 7 - \epsilon})$ where $\epsilon \approx 0.807$.
  • By Master Theorem Case 1:
    $T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$
• Practical Engineering Limitations:
  • Crossover Threshold: The large constant factors introduced by the 18 matrix additions mean Strassen's algorithm is slower than naive multiplication for small matrices. Practical implementations switch to naive multiplication below a cutoff threshold (typically $n \in [64, 128]$).
  • Numerical Stability: Strassen's algorithm exhibits poorer numerical precision and accumulated floating-point rounding errors compared to naive multiplication.
  • Memory Overhead: Creating intermediate matrices consumes additional working memory.

6. Order Statistics and Selection Algorithms

The $i$-th Order Statistic of a set of $n$ elements is the $i$-th smallest element.

• Minimum element: $i = 1$
• Maximum element: $i = n$
• Median element: $i = \lfloor (n + 1) / 2 \rfloor$ (lower median) or $\lceil (n + 1) / 2 \rceil$ (upper median)

6.1 Simultaneous Minimum and Maximum

Finding the minimum of an array requires $n - 1$ comparisons; finding the maximum independently requires another $n - 1$ comparisons, totaling $2n - 2$ comparisons.
By processing elements in pairs, both minimum and maximum can be determined simultaneously in at most $\mathbf{\lfloor 3n/2 \rfloor}$ comparisons:

1. Initialize min and max using the first 1 or 2 elements (1 comparison).
2. For each remaining pair of elements $(A[j], A[j+1])$:
   • Compare $A[j]$ and $A[j+1]$ (1 comparison).
   • Compare the smaller element against the global min (1 comparison).
   • Compare the larger element against the global max (1 comparison).
3. Total comparisons: $3$ comparisons for every 2 elements $\implies \approx \frac{3}{2} n$ comparisons, representing a 25% efficiency gain over independent scans.

6.2 Randomized Selection (Quickselect)

Quickselect, developed by Tony Hoare, adapts the partitioning principle of Quick Sort to locate the $k$-th smallest element without fully sorting the array.

CODECopy Code
QUICKSELECT(A, p, r, k)
1  if p == r
2      return A[p]
3  q = RANDOMIZED-PARTITION(A, p, r)
4  i = q - p + 1                    // Number of elements in low partition
5  if k == i
6      return A[q]                  // Pivot is the k-th smallest!
7  else if k < i
8      return QUICKSELECT(A, p, q - 1, k)
9  else
10     return QUICKSELECT(A, q + 1, r, k - i)

• Fundamental Distinction from Quick Sort: While Quick Sort recursively conquers both partitions ($2 T(n/2)$), Quickselect recurses into only the single partition containing the $k$-th element, discarding the other half.
• Complexity:
  • Average-Case: Under balanced partitions, $T(n) = T(n/2) + \Theta(n)$. By Master Theorem Case 3, $T(n) = \Theta(n)$ (linear time).
  • Worst-Case: If partitions are maximally unbalanced ($0$ and $n-1$), the recurrence degenerates to $T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$.

6.3 Deterministic Linear-Time Selection: Median-of-Medians (BFPRT Algorithm)

In 1973, Blum, Floyd, Pratt, Rivest, and Tarjan (BFPRT) designed a deterministic selection algorithm that guarantees $\mathcal{O}(n)$ running time in the worst case by ensuring a well-balanced pivot.

CODECopy Code
               Array of n elements partitioned into groups of 5
       ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
Row 1  │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │
Row 2  │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │
Row 3  │ m │ │ m │ │ m │ │ m │ │ M │ │ m │ │ m │ │ m │ │ m │ │ m │ ◄── Median-of-Medians (M)
Row 4  │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │
Row 5  │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │
       └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘

Step-by-Step Algorithmic Execution:

1. Partition into Groups of 5: Divide the $n$ elements into $\lceil n/5 \rceil$ groups of 5 elements each (with at most one final group containing the remaining $n \bmod 5$ elements).
2. Find Median of Each Group: Sort each 5-element group (taking $\mathcal{O}(1)$ time per group) to determine its median. This produces a sequence of $\lceil n/5 \rceil$ medians. Total cost for this step: $\mathcal{O}(n)$.
3. Find the Median-of-Medians ($x$): Recursively call SELECT on the $\lceil n/5 \rceil$ medians to find their median $x$:
   $\text{Cost} = T(\lceil n/5 \rceil)$
4. Partition Around Pivot $x$: Partition the original array around pivot $x$ using standard two-way partitioning. Let $k$ be the rank of $x$.
5. Recurse: If $i = k$, return $x$. If $i < k$, recurse into the low side; otherwise, recurse into the high side for rank $i - k$.

Guaranteeing Balanced Partitions:

At least half of the $\lceil n/5 \rceil$ medians are greater than or equal to $x$. Each such median represents a group of 5 where at least 3 elements are $\ge$ the group median, and hence $\ge x$.
Excluding the group containing $x$ and the short group, the number of elements guaranteed to be strictly greater than $x$ is at least:
$3 \left( \left\lceil \frac{1}{2} \left\lceil \frac{n}{5} \right\rceil \right\rceil - 2 \right) \ge \frac{3n}{10} - 6$
By symmetry, at least $\frac{3n}{10} - 6$ elements are smaller than $x$.
Consequently, in the worst case, the recursive call in Step 5 executes on at most:
$n - \left(\frac{3n}{10} - 6\right) = \frac{7n}{10} + 6 \quad \text{elements}$

Recurrence Relation and Proof of Linear Time:

$T(n) \le T(\lceil n/5 \rceil) + T(7n/10 + 6) + \mathcal{O}(n)$

Using substitution, we prove $T(n) \le c n$ for some constant $c$:
$T(n) \le c \left(\frac{n}{5} + 1\right) + c \left(\frac{7n}{10} + 6\right) + a n = c \frac{9n}{10} + 7c + a n = c n + \left(-\frac{c n}{10} + 7c + a n\right)$
To satisfy $T(n) \le c n$, we require:
$-\frac{c n}{10} + 7c + a n \le 0 \iff c \left(\frac{n}{10} - 7\right) \ge a n$
Assuming $n \ge 140$ (so that $n/10 - 7 \ge n/20$):
$\frac{c n}{20} \ge a n \implies c \ge 20 a$
Thus, choosing $c \ge 20a$ establishes that $T(n) = \mathcal{O}(n)$ unconditionally in the worst case.

Note on Group Size: Why groups of 5? If groups of 3 were chosen, the recurrence would be $T(n) \le T(n/3) + T(2n/3) + \mathcal{O}(n)$. The subproblem fractions sum to $1/3 + 2/3 = 1$, leading to $T(n) = \Theta(n \lg n)$ rather than linear time. Groups of 5 yield $1/5 + 7/10 = 9/10 < 1$, ensuring geometric decay and guaranteed $\mathcal{O}(n)$ linear performance.