W3. Divide and Conquer, Master Theorem, Efficient Sorting

Author

Nikolai Kudasov

Published

February 2, 2026

1. Summary

1.1 Introduction to Divide and Conquer

Divide and Conquer is a fundamental algorithm design paradigm that solves a problem by breaking it down into smaller, independent subproblems of the same type, solving each subproblem independently, and then combining the solutions to produce the answer to the original problem. This approach is particularly powerful for problems that naturally decompose into independent parts.

The divide-and-conquer strategy is recursive in nature: each recursive call solves a smaller instance of the same problem until reaching a base case (subproblem small enough to solve directly), at which point the algorithm returns and combines results as it unwinds the recursion.

1.1.1 The Three Parts of Divide and Conquer

Every divide-and-conquer algorithm has three essential components:

  1. Divide: Break the problem into smaller subproblems of the same type, typically reducing the input size. For example, split an array into two halves, or reduce the exponent in exponentiation.
  2. Conquer: Solve each subproblem recursively. The base case defines when subproblems are small enough to solve directly without further recursion (e.g., an array of one element is already “sorted”).
  3. Combine: Merge or integrate the solutions of the subproblems to produce the solution to the original problem. This step must be efficient — if combining is expensive, it can dominate the overall running time.

Real-world analogy: Imagine you need to organize a large library. Rather than sorting every book individually, divide the books into smaller sections, sort each section (conquer), then merge the sorted sections back together (combine). The key insight is that merging two sorted lists is much faster than sorting an unsorted one.

1.2 Analyzing Divide-and-Conquer Algorithms: Recurrence Relations

The running time of a divide-and-conquer algorithm is naturally expressed as a recurrence relation — a mathematical equation that defines \(T(n)\) (running time for input size \(n\)) in terms of the running time of smaller instances.

A typical recurrence has the form: \[T(n) = \begin{cases} \Theta(1) & \text{if } n \le n_0 \text{ (base case)} \\ a \cdot T(n/b) + f(n) & \text{otherwise (recursive case)} \end{cases}\]

  • \(a\): Number of subproblems created in the divide step
  • \(n/b\): Size of each subproblem (the input is divided by \(b\))
  • \(f(n)\): Time spent on divide and combine operations (not including the recursive calls)

Example: For merge sort, we create \(a = 2\) subproblems of size \(n/b = n/2\), and spend \(f(n) = \Theta(n)\) time merging. This gives: \[T(n) = 2 \cdot T(n/2) + \Theta(n)\]

Solving recurrence relations is crucial because it tells us the overall asymptotic complexity of the algorithm.

1.2.1 Methods for Solving Recurrence Relations

There are three main approaches to finding closed-form solutions for recurrences:

  1. Substitution method: Guess a bound and prove it correct by mathematical induction. While this works, it requires intuition about what the answer should be.
  2. Recursion tree method: Visualize the recursion as a tree, sum the work at each level, and use properties of geometric series or other summation techniques. This method provides more intuition about where the time is spent (early vs. late in the recursion).
  3. Master method: A general recipe for solving many recurrences of the specific form \(T(n) = a \cdot T(n/b) + f(n)\). This is the most practical method and requires only identifying the parameters \(a\), \(b\), and \(f(n)\).
1.3 The Master Theorem

The Master Theorem (Cormen et al. 2022, Theorem 4.1) provides a direct solution for recurrences of the form: \[T(n) = a \cdot T(n/b) + f(n)\]

where \(a \ge 1\) and \(b > 1\) are constants, and \(f(n)\) is an asymptotically nonnegative function. The key insight is to compare the growth of \(f(n)\) (cost of divide and combine) with the growth of \(n^{\log_b a}\) (cost of all recursion calls summed together).

1.3.1 The Three Cases

Case 1 — Recursion dominates: If \(f(n)\) is significantly smaller than \(n^{\log_b a}\), the recursion itself dominates the running time.

\[\text{If } \exists\, \epsilon > 0 \text{ such that } f(n) = O(n^{\log_b a - \epsilon}), \text{ then } T(n) = \Theta(n^{\log_b a})\]

Intuition: Most of the work happens in the leaves of the recursion tree. There are \(n^{\log_b a}\) leaf nodes (base cases), each doing \(\Theta(1)\) work, totaling \(\Theta(n^{\log_b a})\).

Case 2 — Recursion and divide-combine are balanced: If \(f(n)\) grows at roughly the same rate as \(n^{\log_b a}\) (with possible logarithmic factors), they share the work approximately equally.

\[\text{If } \exists\, k \ge 0 \text{ such that } f(n) = \Theta(n^{\log_b a} \log^k n), \text{ then } T(n) = \Theta(n^{\log_b a} \log^{k+1} n)\]

Intuition: Work is distributed across all levels of the recursion. If work is distributed evenly, we multiply by the number of levels, which is \(\log_b n\). If \(f(n)\) already has logarithmic factors, they accumulate.

Case 3 — Divide-combine dominates: If \(f(n)\) is significantly larger than \(n^{\log_b a}\), the divide-and-combine step dominates, and the recursion contributes relatively little.

\[\text{If } \exists\, \epsilon > 0 \text{ such that } f(n) = \Omega(n^{\log_b a + \epsilon}), \text{ and the **regularity condition** } af(n/b) \le c \cdot f(n)\] \[\text{holds for some } c < 1 \text{ and all sufficiently large } n, \text{ then } T(n) = \Theta(f(n))\]

Intuition: The work is dominated by the top level of the recursion (the initial divide and combine). The regularity condition ensures that the recurrence remains well-behaved — the cost of combining doesn’t increase by too much when moving up the recursion tree.

What is the “regularity condition”? It says that after dividing the problem into subproblems and combining them at level \(i\), the work at level \(i\) should not be significantly more than the work at level \(i-1\). This ensures that the series of combine costs forms a convergent geometric series, so the total work is dominated by the topmost level.

1.3.2 Understanding \(n^{\log_b a}\)

This quantity represents the total cost of the recursion itself — sum of the work done in all recursive calls (excluding the divide/combine operations). Here’s why:

  • There are \(a\) subproblems at level 1, each of size \(n/b\). Recursively, they contribute \(a \cdot T(n/b)\).
  • At level 0 (the root), there is \(a^0 = 1\) problem of size \(n\).
  • At level \(k\), there are \(a^k\) problems, each of size \(n/b^k\).
  • The recursion has depth \(\log_b n\) (the size shrinks by factor \(b\) at each level).
  • Total number of leaf nodes: \(a^{\log_b n} = n^{\log_b a}\).
1.4 Maximum Subarray Problem

The Maximum Subarray Problem is a classic example of a problem that yields to divide-and-conquer approach and demonstrates how this technique can improve upon naive algorithms.

1.4.1 Problem Definition

Input: A sequence of \(n\) numbers \(\langle a_1, a_2, \dots, a_n \rangle\).

Output: Indices \(l\) and \(r\) such that \(\sum_{i=l}^{r} a_i \ge \sum_{i=l'}^{r'} a_i\) for any \(1 \le l' \le r' \le n\). Find the contiguous subarray with the maximum sum.

Practical application: This problem arises in financial analysis where you track changes in stock price (profit/loss). A maximum subarray represents the best opportunity to buy and sell a stock. You might also see it in analyzing temperature changes or seismic data — finding when conditions were consistently “good” or “bad.”

Example: For the array \([2, -1, 3, 4, 1, -5]\), the subarray \([-1, 3, 4, 1]\) (from index 2 to 5) has sum 7, which turns out to be maximal.

1.4.2 Naive Brute-Force Approach

The straightforward algorithm checks every possible subarray:

for l = 1 to n
  for r = l to n
    compute sum of A[l...r]
    if sum > best_sum:
      best_sum = sum
      best_l = l
      best_r = r

The inner loops check all \(\binom{n+1}{2} = \Theta(n^2)\) possible subarrays. Even with optimization (computing sums incrementally), this is \(\Theta(n^2)\) in the best case, which is slow for large inputs.

1.4.3 Divide-and-Conquer Solution

The key insight is that a maximum subarray in \(A[l \dots r]\) must be located in one of three places:

  1. Entirely in the left half — \(A[l \dots m]\) where \(m = \lfloor (l + r) / 2 \rfloor\)
  2. Entirely in the right half — \(A[m + 1 \dots r]\)
  3. Crossing the middle — spans from some index in the left half to some index in the right half

For cases 1 and 2, we recurse. For case 3, we need a different approach because no recursion can represent subarrays that cross the division point.

The crossing subarray can be found efficiently: start from the middle and expand left and right, tracking the maximum sum at each step. This is \(O(n)\) rather than recursive.

Algorithm structure:

FIND-MAXIMUM-SUBARRAY(A, l, r):
  if l == r:
    return (l, r, A[l])  // base case: single element
  else:
    m = floor((l + r) / 2)
    (left_l, left_r, left_sum) = FIND-MAXIMUM-SUBARRAY(A, l, m)
    (right_l, right_r, right_sum) = FIND-MAXIMUM-SUBARRAY(A, m + 1, r)
    (cross_l, cross_r, cross_sum) = FIND-MAX-CROSSING-SUBARRAY(A, l, m, r)

    // Return the maximum of the three cases
    if left_sum >= right_sum and left_sum >= cross_sum:
      return (left_l, left_r, left_sum)
    else if right_sum >= left_sum and right_sum >= cross_sum:
      return (right_l, right_r, right_sum)
    else:
      return (cross_l, cross_r, cross_sum)

The helper function FIND-MAX-CROSSING-SUBARRAY finds the best crossing subarray:

FIND-MAX-CROSSING-SUBARRAY(A, l, m, r):
  // Find the best sum starting from m and extending left
  left_sum = -∞
  sum = 0
  for i = m down to l:
    sum = sum + A[i]
    if sum > left_sum:
      left_sum = sum
      max_left = i

  // Find the best sum starting from m+1 and extending right
  right_sum = -∞
  sum = 0
  for j = m + 1 to r:
    sum = sum + A[j]
    if sum > right_sum:
      right_sum = sum
      max_right = j

  return (max_left, max_right, left_sum + right_sum)

This helper runs in \(\Theta(n)\) because it scans from the middle to both ends.

1.4.4 Complexity Analysis

Recurrence: \[T(n) = 2 \cdot T(n/2) + \Theta(n)\]

  • Divide: \(\Theta(1)\) — find the midpoint
  • Conquer: Two recursive calls, each on \(n/2\) elements
  • Combine: \(\Theta(n)\) — find the crossing subarray

Applying the Master Theorem: \(a = 2\), \(b = 2\), \(f(n) = \Theta(n)\).

Compute \(n^{\log_b a} = n^{\log_2 2} = n^1 = n\).

Since \(f(n) = \Theta(n^1) = \Theta(n)\), we apply Case 2 (with \(k = 0\)): \[T(n) = \Theta(n \log n)\]

This is a significant improvement over the \(\Theta(n^2)\) brute-force approach, especially for large \(n\).

1.5 Merge Sort

Merge Sort is one of the most important sorting algorithms. It is a pure divide-and-conquer algorithm that demonstrates how the paradigm yields efficient, practical solutions.

1.5.1 Overview and Properties
  • Type: Divide-and-conquer
  • Time complexity: \(\Theta(n \log n)\) — guaranteed, both best and worst case
  • Space complexity: \(\Theta(n)\) — requires auxiliary space for merging
  • Stability: Stable — equal elements maintain their original relative order
  • In-place: Not in-place — requires temporary arrays during merging

The stability property is important for sorting objects with multiple fields. For example, if you have employee records sorted by name, then sort by department, a stable sort keeps employees with the same department in name order.

1.5.2 Algorithm Idea
  1. Divide: Split the array into two halves at the midpoint.
  2. Conquer: Recursively sort the left and right halves.
  3. Combine: Merge the two sorted halves into a single sorted array.

Key insight: Merging two already sorted arrays is straightforward and linear in the combined size. This is much faster than sorting an unsorted array.

1.5.3 Merge Operation

Merging two sorted arrays \(L\) and \(R\) into a sorted array \(A\):

  1. Maintain pointers i and j at the start of \(L\) and \(R\), respectively.
  2. Compare L[i] and R[j]. Copy the smaller element to \(A\) and advance the corresponding pointer.
  3. When one array is exhausted, copy the remaining elements from the other array.

Example: Merging \(L = [1, 4, 5, 6, 8]\) and \(R = [2, 3, 4, 7, 9]\):

  • Compare 1 and 2: copy 1 → \(A = [1]\)
  • Compare 4 and 2: copy 2 → \(A = [1, 2]\)
  • Compare 4 and 3: copy 3 → \(A = [1, 2, 3]\)
  • Compare 4 and 4: copy 4 from \(L\) (to maintain stability) → \(A = [1, 2, 3, 4]\)
  • Continue: → \(A = [1, 2, 3, 4, 4, 5, 6, 7, 8, 9]\)

Important for stability: When comparing equal elements from \(L\) and \(R\), always prefer the element from the left array \(L\). This preserves the original relative order.

Time complexity: \(\Theta(n)\) where \(n = |L| + |R|\), because each element is examined exactly once.

1.5.4 Pseudocode
MERGE-SORT(A, p, r):
  if p >= r:
    return  // zero or one element is already sorted
  q = floor((p + r) / 2)
  MERGE-SORT(A, p, q)        // sort left half
  MERGE-SORT(A, q + 1, r)    // sort right half
  MERGE(A, p, q, r)          // merge the two halves
1.5.5 Complexity Analysis

Recurrence: \[T(n) = 2 \cdot T(n/2) + \Theta(n)\]

  • Divide: \(\Theta(1)\) — computing the midpoint
  • Conquer: Two recursive calls on arrays of size \(n/2\)
  • Combine: \(\Theta(n)\) — merging takes linear time

Applying the Master Theorem: \(a = 2\), \(b = 2\), \(f(n) = \Theta(n)\).

Since \(n^{\log_2 2} = n\) and \(f(n) = \Theta(n)\), we use Case 2 (with \(k = 0\)): \[T(n) = \Theta(n \log n)\]

Space complexity: We need \(\Theta(n)\) auxiliary space for temporary arrays during merging. This is the main disadvantage compared to in-place sorting algorithms.

1.6 Quicksort

Quicksort is one of the most popular sorting algorithms in practice, despite having a poor worst-case complexity. With proper pivot selection, it achieves excellent average-case performance and minimal space overhead.

1.6.1 Overview and Properties
  • Type: Divide-and-conquer
  • Time complexity: \(\Theta(n^2)\) worst case, \(\Theta(n \log n)\) average case
  • Space complexity: \(\Theta(\log n)\) for the recursion stack
  • Stability: Not stable — the partitioning process may move equal elements
  • In-place: In-place — partitioning modifies the array in place with minimal extra memory

Quicksort’s popularity stems from its excellent average-case performance and minimal space requirements. Most practical implementations use randomized pivot selection to achieve \(\Theta(n \log n)\) expected time even on adversarial inputs.

1.6.2 Algorithm Idea
  1. Divide: Choose a pivot element and partition the array into three groups:
    • Elements less than or equal to the pivot
    • The pivot itself
    • Elements greater than the pivot
  2. Conquer: Recursively sort the left partition (elements \(\le\) pivot) and the right partition (elements \(>\) pivot).
  3. Combine: Concatenation — since the pivot is already in its final position and both partitions are sorted, the entire array is sorted.

Key insight: Unlike merge sort, the combine step is implicit. No additional work is needed after recursive calls.

1.6.3 Partitioning Algorithm

The partition operation is the core of quicksort. It rearranges the array so that all elements less than or equal to a chosen pivot come before it, and all elements greater come after.

In-place partition algorithm:

PARTITION(A, p, r):
  x = A[r]           // choose last element as pivot
  i = p - 1          // index of the high end of the low partition

  for j = p to r - 1:     // process each element except the pivot
    if A[j] <= x:
      i = i + 1
      exchange A[i] with A[j]  // move element to low partition

  exchange A[i + 1] with A[r]  // place pivot in its final position
  return i + 1        // return pivot's final index

Invariants: At each step:

  • \(A[p \dots i]\): elements \(\le x\) (low partition)
  • \(A[i+1 \dots j-1]\): elements \(> x\) (high partition)
  • \(A[j \dots r-1]\): unprocessed
  • \(A[r]\): pivot

Time complexity: \(\Theta(n)\), because we scan each element once.

1.6.4 Pseudocode
QUICKSORT(A, p, r):
  if p < r:
    q = PARTITION(A, p, r)     // partition and get pivot index
    QUICKSORT(A, p, q - 1)     // sort elements <= pivot
    QUICKSORT(A, q + 1, r)     // sort elements > pivot
1.6.5 Worst-Case Complexity

The worst case occurs when the pivot is always the smallest or largest element, resulting in highly unbalanced partitions (one partition has \(n-1\) elements, the other has 0).

Recurrence: \[T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + \Theta(n)\]

Expanding: \[T(n) \le T(n-1) + cn \le T(n-2) + c(n-1) + cn \le \dots \le T(0) + c \cdot 2 + c \cdot 3 + \dots + cn\] \[= c \sum_{i=2}^{n} i = c \cdot \frac{n(n+1)}{2} - c = \Theta(n^2)\]

This happens when the input is already sorted (or reverse-sorted) and you always pick the first (or last) element as the pivot.

1.6.6 Best-Case Complexity

The best case occurs when the pivot divides the array into two nearly equal halves.

Recurrence: \[T(n) = 2 \cdot T(n/2) + \Theta(n)\]

Applying the Master Theorem: \(a = 2\), \(b = 2\), \(f(n) = \Theta(n)\).

Since \(f(n) = \Theta(n^{\log_2 2})\), we use Case 2 (with \(k = 0\)): \[T(n) = \Theta(n \log n)\]

1.6.7 Average-Case Complexity

With a random pivot (or a good heuristic like “median of three”), the algorithm typically divides the array reasonably well. The analysis shows that even if partitions are not perfectly balanced, the expected time is still \(\Theta(n \log n)\).

Intuition: Even if one partition has 1/4 of the elements and the other has 3/4, the sum of partition sizes across levels still decreases exponentially, giving logarithmic depth.

Formally (Cormen et al. 2022, §7.4), the expected running time of randomized quicksort is: \[E[T(n)] = \Theta(n \log n)\]

1.7 Comparison of Sorting Algorithms

Different sorting algorithms have different trade-offs:

Algorithm Best Case Average Case Worst Case Space Stable In-place
Insertion Sort \(\Theta(n)\) \(\Theta(n^2)\) \(\Theta(n^2)\) \(\Theta(1)\) Yes Yes
Merge Sort \(\Theta(n \log n)\) \(\Theta(n \log n)\) \(\Theta(n \log n)\) \(\Theta(n)\) Yes No
Quicksort \(\Theta(n \log n)\) \(\Theta(n \log n)\) \(\Theta(n^2)\) \(\Theta(\log n)\) No Yes
Heapsort \(\Theta(n \log n)\) \(\Theta(n \log n)\) \(\Theta(n \log n)\) \(\Theta(1)\) No Yes

Selection criteria:

  • Merge Sort: Use when worst-case \(\Theta(n \log n)\) is required or when stability is essential. Acceptable space overhead.
  • Quicksort: Use for general-purpose sorting. Excellent average case and minimal space. Avoid on already-sorted or nearly-sorted data without random pivot selection.
  • Insertion Sort: Use for small arrays (typically \(n < 20\)) or when the array is already nearly sorted. Very efficient in these cases due to low overhead.
  • Hybrid approach: Real-world implementations often use quicksort for general partitioning but switch to insertion sort for small subarrays (typical threshold: \(n \le 10\)).

2. Definitions

  • Divide-and-Conquer Algorithm: A recursive algorithm that solves a problem by breaking it into smaller independent subproblems of the same type, solving each subproblem recursively (conquer), and combining the solutions.
  • Divide: The step where the problem is partitioned into smaller subproblems, typically reducing the input size.
  • Conquer: The step where subproblems are solved recursively until they reach a base case (subproblem small enough to solve directly).
  • Combine: The step where solutions to subproblems are merged or integrated to produce the solution to the original problem.
  • Recurrence Relation: A mathematical equation that expresses the running time \(T(n)\) of a recursive algorithm in terms of the running time of smaller instances, used to analyze divide-and-conquer algorithms.
  • Master Theorem: A direct method for solving recurrence relations of the form \(T(n) = a \cdot T(n/b) + f(n)\) by comparing \(f(n)\) with \(n^{\log_b a}\).
  • Case 1 (Master Theorem): When \(f(n) = O(n^{\log_b a - \epsilon})\) for some \(\epsilon > 0\), the recursion dominates and \(T(n) = \Theta(n^{\log_b a})\).
  • Case 2 (Master Theorem): When \(f(n) = \Theta(n^{\log_b a} \log^k n)\) for some \(k \ge 0\), divide and recursion are balanced and \(T(n) = \Theta(n^{\log_b a} \log^{k+1} n)\).
  • Case 3 (Master Theorem): When \(f(n) = \Omega(n^{\log_b a + \epsilon})\) for some \(\epsilon > 0\) and the regularity condition holds, divide-combine dominates and \(T(n) = \Theta(f(n))\).
  • Regularity Condition: The condition \(af(n/b) \le c \cdot f(n)\) (for some \(c < 1\)) in Case 3 of the Master Theorem, ensuring that the recurrence is well-behaved and the series of costs converges.
  • Maximum Subarray Problem: The problem of finding a contiguous subarray with the maximum sum, frequently arising in financial analysis and time-series data.
  • Brute Force Approach: An algorithm that tries all possible solutions systematically, often inefficient but straightforward to implement and understand.
  • Merge Sort: A stable, divide-and-conquer sorting algorithm that achieves \(\Theta(n \log n)\) time in all cases but requires \(\Theta(n)\) auxiliary space.
  • Merging: The operation of combining two sorted arrays into a single sorted array in linear time.
  • Stability (in sorting): A property where equal elements maintain their original relative order after sorting.
  • Quicksort: An in-place, divide-and-conquer sorting algorithm that achieves \(\Theta(n \log n)\) average time but \(\Theta(n^2)\) worst-case time, with excellent practical performance on random inputs.
  • Pivot: The element chosen to partition the array in quicksort, around which elements are rearranged into smaller and larger groups.
  • Partition: The operation in quicksort that rearranges an array so that elements less than or equal to a pivot precede those greater than the pivot.
  • In-place Sorting: A sorting algorithm that sorts the array without requiring additional space proportional to the input size, using only \(O(1)\) or \(O(\log n)\) extra space.

3. Formulas

  • Master Theorem Recurrence Form: \(T(n) = a \cdot T(n/b) + f(n)\) where \(a \ge 1\), \(b > 1\), and \(f(n) \ge 0\)
  • Case 1 (Master Theorem): If \(f(n) = O(n^{\log_b a - \epsilon})\) for some \(\epsilon > 0\), then \(T(n) = \Theta(n^{\log_b a})\)
  • Case 2 (Master Theorem): If \(f(n) = \Theta(n^{\log_b a} \log^k n)\) for some \(k \ge 0\), then \(T(n) = \Theta(n^{\log_b a} \log^{k+1} n)\)
  • Case 3 (Master Theorem): If \(f(n) = \Omega(n^{\log_b a + \epsilon})\) for some \(\epsilon > 0\) and \(af(n/b) \le cf(n)\) for \(c < 1\), then \(T(n) = \Theta(f(n))\)
  • Cost of Recursion: \(n^{\log_b a} = a^{\log_b n}\) represents the total work in all recursive calls across all levels of the recursion tree
  • Maximum Subarray (Divide-and-Conquer Recurrence): \(T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)\)
  • Maximum Subarray (Brute Force Complexity): \(T(n) = \Theta(n^2)\) checking all \(O(n^2)\) subarrays
  • Merge Sort Recurrence: \(T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)\)
  • Merge Sort Space Complexity: \(\Theta(n)\) auxiliary space for merging
  • Quicksort Best/Average Recurrence: \(T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)\)
  • Quicksort Worst-Case Recurrence: \(T(n) = T(n-1) + \Theta(n) = \Theta(n^2)\)
  • Partition Time Complexity: \(\Theta(n)\) for scanning and rearranging elements

4. Examples

4.1. Analyze Time Complexity of Linked List Processing Function (Problem Set 3, Task 1)

Determine the worst-case time complexity of the following function in terms of the input linked list size \(n\):

/* L is a linked list of size n */
function process(L)
  if L.is_empty()
    return 0
  else if L.size() == 1
    return L.head.value
  else
    lists = new array of 3 empty linked lists
    i = 0
    A = L.head
    while A is not None
      if (i mod 4) > 0
        lists[i mod 4].add(A.value)
      A = A.next
      i = i + 1
    result = process(lists[1])
    result += process(lists[2])
    result += process(lists[3])
    return result

(a) Write down the recurrence relation for \(T(n)\)

(b) Find the asymptotic complexity \(T(n)\) using the substitution method, recursion tree method, or master method. Work through each step explicitly with formal definitions or explicit references to the Master Theorem.

Click to see the solution

Key Concept: Analyze the function’s structure to determine how many elements go into each recursive subproblem, then set up and solve the recurrence.

Part (a): Recurrence Relation

  1. Analyze the function structure:

    • Base cases: Empty list and single-element list are handled in \(\Theta(1)\)
    • Recursive case: The function iterates through all \(n\) elements once (while loop), distributing them into three sublists
    • The key question: How many elements go into each sublist?

  2. Determine distribution into sublists:

    • Elements are added to lists[i mod 4] only when (i mod 4) > 0
    • For indices \(i = 0, 1, 2, \ldots, n-1\):
      • \(i \equiv 0 \pmod{4}\): element is NOT added (skipped)
      • \(i \equiv 1 \pmod{4}\): element added to lists[1]
      • \(i \equiv 2 \pmod{4}\): element added to lists[2]
      • \(i \equiv 3 \pmod{4}\): element added to lists[3]
    • Among every 4 consecutive elements, exactly 3 are distributed (indices 1, 2, 3 out of 0, 1, 2, 3)
    • In total, approximately \(3n/4\) elements are distributed into the three sublists

  3. Precise analysis:

    • When \(n = 4k\) (exactly divisible by 4): exactly \(3k\) elements are distributed, so each list has about \(k = n/4\) elements
    • When \(n = 4k + r\) (with \(0 < r < 4\)): roughly \(3n/4\) elements total
    • In the worst case, the distribution is: \(\lceil n/4 \rceil\), \(\lceil n/4 \rceil\), \(\lceil n/4 \rceil\) elements (approximately equal)

  4. Recurrence relation: \[T(n) = \begin{cases} \Theta(1) & \text{if } n \le 1 \\ \Theta(n) + 3T(n/4) & \text{if } n > 1 \end{cases}\]

    where the \(\Theta(n)\) term represents the work done in the while loop (traversing all \(n\) elements), and \(3T(n/4)\) represents the three recursive calls on sublists of size approximately \(n/4\) each.

Part (b): Asymptotic Complexity Using Master Theorem

  1. Identify parameters:

    • \(a = 3\) (three recursive calls)
    • \(b = 4\) (each subproblem has size approximately \(n/4\))
    • \(f(n) = \Theta(n)\) (work in the non-recursive part, the while loop)

  2. Compute the recursion cost: \[n^{\log_b a} = n^{\log_4 3} = n^{\log 3 / \log 4} = n^{\approx 0.792}\]

    More precisely, \(\log_4 3 = \frac{\log 3}{\log 4} = \frac{\ln 3}{\ln 4} \approx 0.7924\)

  3. Compare \(f(n) = \Theta(n)\) with \(n^{\log_4 3} = n^{\approx 0.792}\):

    • \(f(n) = \Theta(n^1)\)
    • \(n^{\log_4 3} = \Theta(n^{0.792})\)
    • Since \(1 > 0.792\), we have \(f(n) \gg n^{\log_4 3}\), so \(f(n)\) dominates

  4. Check Case 3 of Master Theorem:

    • We need: \(f(n) = \Omega(n^{\log_4 3 + \epsilon})\) for some \(\epsilon > 0\)
    • Choose \(\epsilon = 0.208\), so \(\log_4 3 + \epsilon = 1\)
    • Then: \(n = \Omega(n^{1}) = \Omega(n)\) ✓
    • Check regularity condition: \(af(n/b) \le c \cdot f(n)\) for some \(c < 1\)
    • \(3 \cdot (n/4) = 3n/4\)
    • We need: \(3n/4 \le c \cdot n\), which holds with \(c = 3/4 < 1\) ✓

  5. Apply Case 3: \[T(n) = \Theta(f(n)) = \Theta(n)\]

Answer:

(a) \(T(n) = 3T(n/4) + \Theta(n)\)

(b) Using the Master Theorem (Case 3): \(T(n) = \Theta(n)\)

The function runs in linear time despite the recursive structure, because the \(\Theta(n)\) work done in each recursive level dominates the exponentially increasing number of subproblems (which shrink exponentially in size).

4.2. Solve Recurrence Relations Using Master Method (Problem Set 3, Task 2)

Solve each of the following recurrence relations using the Master Theorem. For each, state whether the master method applies, indicate which case (1, 2, or 3) applies if it does, verify the conditions explicitly, and provide the final answer in \(\Theta\)-notation.

  1. \(T(n) = 4T(n/16) + \sqrt{n} \cdot \log_2 n\)
  2. \(T(n) = 5T(4n/9) + n^2\)
  3. \(T(n) = 9T(n/4) + \log_2(n!)\)
  4. \(T(n) = 3T(\sqrt[3]{n}) + n\)
  5. \(T(n) = \frac{1}{2026}T(2026n) + n\log_{2026}n\)
Click to see the solution

(1) \(T(n) = 4T(n/16) + \sqrt{n} \cdot \log_2 n\)

  1. Identify parameters:

    • \(a = 4\), \(b = 16\), \(f(n) = \sqrt{n} \cdot \log_2 n = n^{1/2} \log_2 n\)

  2. Compute recursion cost: \[n^{\log_b a} = n^{\log_{16} 4} = n^{\log_{16} 4}\]

    Note: \(\log_{16} 4 = \frac{\log 4}{\log 16} = \frac{2\log 2}{4\log 2} = \frac{2}{4} = \frac{1}{2}\)

    So \(n^{\log_{16} 4} = n^{1/2} = \sqrt{n}\)

  3. Compare \(f(n)\) with \(n^{1/2}\):

    • \(f(n) = n^{1/2} \log_2 n\)
    • \(n^{\log_{16} 4} = n^{1/2}\)
    • We have \(f(n) = \Theta(n^{1/2} \log^1 n)\), which matches Case 2 with \(k = 1\)

  4. Apply Case 2 (Cormen et al., Theorem 4.1):

    • Condition: \(f(n) = \Theta(n^{\log_b a} \log^k n)\) for some \(k \ge 0\)
    • Here: \(k = 1\) ✓
    • Result: \(T(n) = \Theta(n^{\log_b a} \log^{k+1} n) = \Theta(\sqrt{n} \log^2 n)\)

Answer: \(T(n) = \Theta(\sqrt{n} \log^2 n)\) (Case 2)

(2) \(T(n) = 5T(4n/9) + n^2\)

  1. Check applicability of Master Theorem:
    • Standard form: \(T(n) = aT(n/b) + f(n)\) requires \(b > 1\) and the subproblem size to be \(n/b\)
    • Here: subproblem size is \(\frac{4n}{9}\), which is NOT of the form \(n/b\) (since \(4/9 \ne 1/b\) for any \(b > 1\))
    • For example, if \(n/b = 4n/9\), then \(b = 9/4\), which is allowed, but then we have \(aT(n/b) = 5T(n \cdot 9/4) = 5T(9n/4)\), which means the subproblems grow, not shrink
    • Master Theorem does not apply because the subproblems grow in size rather than shrink
  2. Why Master Theorem fails:
    • The recurrence has \(T(4n/9)\) instead of \(T(n/b)\) with \(b > 1\)
    • This violates the standard form of the Master Theorem
    • While \(4n/9 = (4/9)n \approx 0.444n\), the subproblems do shrink, but we have 5 subproblems of size \(4n/9\), not of size \(n/b\).
    • This is not in the standard form \(T(n) = aT(n/b) + f(n)\). The Master Theorem, as stated in Cormen et al., requires the subproblems to be of size exactly \(n/b\).
  3. Conclusion:
    • Master Theorem is not applicable to this recurrence.
    • To solve it, we would use other techniques (substitution method or recursion tree method), but those are beyond this scope.

Answer: Master method is not applicable. The subproblem size \(4n/9\) does not match the required form \(n/b\).

(3) \(T(n) = 9T(n/4) + \log_2(n!)\)

  1. Simplify \(\log_2(n!)\):

    • By Stirling’s approximation: \(\log(n!) = \Theta(n \log n)\)
    • More precisely: \(\log_2(n!) = \Theta(n \log_2 n)\)
    • So \(f(n) = \Theta(n \log n)\)

  2. Identify parameters:

    • \(a = 9\), \(b = 4\), \(f(n) = \Theta(n \log n)\)

  3. Compute recursion cost: \[n^{\log_b a} = n^{\log_4 9}\]

    Note: \(\log_4 9 = \frac{\log 9}{\log 4} = \frac{2\log 3}{2\log 2} = \frac{\log 3}{\log 2} = \log_2 3 \approx 1.585\)

  4. Compare \(f(n) = n\log n\) with \(n^{\log_2 3} = n^{1.585}\):

    • \(f(n) = n^1 \log n\)
    • \(n^{\log_4 9} = n^{1.585}\)
    • We have \(n^1 < n^{1.585}\), so \(n^{\log_4 9}\) dominates (even with the log factor in \(f(n)\))
    • Check: Is \(n\log n = O(n^{1.585 - \epsilon})\) for some \(\epsilon > 0\)?
    • For \(\epsilon = 0.585\): \(n^{1.585 - 0.585} = n^1 = n\)
    • But \(n\log n \ne O(n)\), so this doesn’t satisfy Case 1
    • Actually, let’s be more careful. We need to check if \(f(n) = O(n^{\log_4 9 - \epsilon})\) for some \(\epsilon > 0\).
    • \(n \log n\) vs. \(n^{1.585}\): as \(n \to \infty\), \(n^{1.585} \gg n\log n\)
    • For any \(\epsilon > 0\), eventually \(n^{1.585}\) dominates \(n\log n\) multiplied by any constant
    • So yes, \(n\log n = O(n^{1.585 - \epsilon})\) for small enough \(\epsilon\) (e.g., \(\epsilon = 0.5\))

  5. Apply Case 1: \[T(n) = \Theta(n^{\log_4 9}) = \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})\]

Answer: \(T(n) = \Theta(n^{\log_2 3})\) (Case 1)

(4) \(T(n) = 3T(\sqrt[3]{n}) + n\)

  1. Check applicability:
    • The subproblem size is \(\sqrt[3]{n} = n^{1/3}\), not \(n/b\) for integer \(b > 1\)
    • Master Theorem does not apply in its standard form
    • (The Master Theorem, as stated, requires \(T(n) = aT(n/b) + f(n)\) with \(b > 1\) being constant)
  2. Alternative approach (substitution method):
    • Let \(m = \log_3 n\), so \(n = 3^m\)
    • Let \(S(m) = T(3^m)\)
    • Then: \(T(n) = 3T(n^{1/3}) + n\)
    • Becomes: \(S(m) = 3S(m/3) + 3^m\) (after substitution and simplification)
    • Wait, let me redo this. If \(n = 3^m\) and subproblem is \(n^{1/3} = 3^{m/3}\):
    • \(T(3^m) = 3T(3^{m/3}) + 3^m\)
    • Set \(S(m) = T(3^m)\): \(S(m) = 3S(m/3) + 3^m\)
    • Now \(3^m\) is a bit awkward. Let’s rewrite: \(S(m) = 3S(m/3) + c \cdot 3^m\) for some constant
    • Actually, this is approximately \(S(m) = 3S(m/3) + 3^m = aS(m/b) + f(m)\) with \(a = 3\), \(b = 3\), \(f(m) = 3^m\)
    • Interpreting as \(S(m) = 3S(m/3) + 2^m\) (in the \(m\) domain), we’d compute \(m^{\log_3 3} = m\)
    • But this is complex; the recurrence in the \(m\) domain doesn’t fit the standard form either.
  3. Conclusion:
    • Master Theorem is not applicable to the original recurrence.

Answer: Master method is not applicable. The subproblem size \(n^{1/3}\) does not fit the standard form \(n/b\) with constant \(b > 1\).

(5) \(T(n) = \frac{1}{2026}T(2026n) + n\log_{2026}n\)

  1. Check applicability:
    • The recurrence has \(\frac{1}{2026}T(2026n)\), meaning the coefficient of \(T\) is less than 1 and the subproblem size is \(2026n\) (larger than \(n\))
    • This is NOT in the standard form \(T(n) = aT(n/b) + f(n)\) with \(a \ge 1\) and \(b > 1\)
    • Master Theorem does not apply because:
      • The coefficient \(\frac{1}{2026} < 1\) violates \(a \ge 1\)
      • The subproblem size \(2026n > n\) means subproblems grow instead of shrink
  2. Why this doesn’t make sense as a recurrence:
    • If subproblems grow in size, the recursion will never reach a base case (for \(n \ge 1\))
    • This is not a valid recurrence relation for an algorithm
  3. Conclusion:
    • Master Theorem is not applicable and the recurrence is malformed.

Answer: Master method is not applicable. The coefficient \(a = \frac{1}{2026} < 1\) violates the requirement \(a \ge 1\), and the subproblem size grows rather than shrinks.

4.3. Analyze Modified Merge Sort with Insertion Sort (Problem Set 3, Task 3)

Consider a modification of merge sort that stops recursive division on arrays of size \(k\) or less (\(k \le n\)). On an array of size \(k\), the “conquer” phase consists of sorting using insertion sort.

(a) Write down the pseudocode of the modified sorting algorithm.

(b) What is the time complexity of the modified sorting algorithm in the worst case (in terms of \(n\) and \(k\))? Give your answer using \(\Theta\)-notation and provide justification.

(c) What is the time complexity of the modified sorting algorithm in the best case (in terms of \(n\) and \(k\))? Give your answer using \(\Theta\)-notation and provide justification.

Click to see the solution

Part (a): Pseudocode

HYBRID-MERGE-SORT(A, p, r, k):
  if r - p + 1 <= k:
    // Base case: use insertion sort for small arrays
    INSERTION-SORT(A, p, r)
  else:
    // Recursive case: divide and merge
    q = floor((p + r) / 2)
    HYBRID-MERGE-SORT(A, p, q, k)           // sort left half
    HYBRID-MERGE-SORT(A, q + 1, r, k)      // sort right half
    MERGE(A, p, q, r)                       // merge the two halves

INSERTION-SORT(A, p, r):
  // Standard insertion sort on A[p..r]
  for i = p + 1 to r:
    key = A[i]
    j = i - 1
    while j >= p and A[j] > key:
      A[j + 1] = A[j]
      j = j - 1
    A[j + 1] = key

Part (b): Worst-Case Time Complexity

  1. Analyze the recursion structure:

    • Arrays larger than size \(k\) are recursively divided and merged
    • Arrays of size \(\le k\) are sorted using insertion sort in \(\Theta(k^2)\) time

  2. Count the number of leaf nodes:

    • The recursion tree has nodes corresponding to subarrays of size \(> k\)
    • Leaf nodes correspond to subarrays of size \(\le k\) that are sorted with insertion sort
    • At each level, subarrays are divided in half until size \(\le k\) is reached
    • Depth of recursion: \(\log_2(n/k)\) levels (dividing by 2 until we reach size \(k\))
    • Number of leaf nodes (subarrays of size \(\le k\)): approximately \(n/k\)

  3. Compute total work:

    • Insertion sort phase: We have \(n/k\) subarrays of size \(\le k\)
      • Each insertion sort call on a subarray of size \(s \le k\) takes \(\Theta(s^2) = \Theta(k^2)\) in the worst case
      • Total work in insertion sorts: \((n/k) \cdot \Theta(k^2) = \Theta(nk)\)
    • Merging phase: At each level \(i\) (from bottom up), we merge subarrays
      • Level just above leaves: merge subarrays of size \(k\) into size \(2k\) — total work \(\Theta(n)\)
      • Next level up: merge subarrays of size \(2k\) into size \(4k\) — total work \(\Theta(n)\)
      • … continuing up the tree …
      • Top level: final merge — total work \(\Theta(n)\)
      • Number of merge levels: \(\log_2(n/k)\)
      • Total merging work: \(\log_2(n/k) \cdot \Theta(n) = \Theta(n \log(n/k))\)

  4. Combine the two phases: \[T_{\text{worst}}(n) = \Theta(nk) + \Theta(n\log(n/k)) = \Theta(nk + n\log(n/k))\]

    Simplify \(\log(n/k) = \log n - \log k\), so this is \(\Theta(nk + n\log n - n\log k) = \Theta(nk + n\log n)\) (since the \(-n\log k\) term is absorbed).

    More carefully:

    • If \(k = O(1)\) (constant), then \(\Theta(nk + n\log n) = \Theta(n + n\log n) = \Theta(n\log n)\)
    • If \(k = \Theta(n)\), then \(\Theta(nk + n\log n) = \Theta(n^2)\) (insertion sort dominates)
    • In general: \(\Theta(nk + n\log(n/k))\)

Answer for (b): \(T_{\text{worst}}(n, k) = \Theta(nk + n\log(n/k))\) or equivalently \(\Theta(nk + n(\log n - \log k))\)

Part (c): Best-Case Time Complexity

  1. Best case for insertion sort:

    • Insertion sort’s best case is \(\Theta(n)\) when the array is already sorted
    • In the best case, each insertion sort call on a subarray of size \(s \le k\) takes \(\Theta(s) = \Theta(k)\) time

  2. Compute total work in best case:

    • Insertion sort phase: \((n/k)\) subarrays, each taking \(\Theta(k)\) in the best case
      • Total: \((n/k) \cdot \Theta(k) = \Theta(n)\)
    • Merging phase:
      • In the best case, two sorted arrays of size \(m\) merge in \(\Theta(m)\) time (when elements of one array are all smaller)
      • Each level of merging still requires comparing and arranging elements, which is \(\Theta(n)\) per level
      • Number of merge levels: \(\log_2(n/k)\)
      • Total merging work: \(\log_2(n/k) \cdot \Theta(n) = \Theta(n\log(n/k))\)

  3. Combine the two phases: \[T_{\text{best}}(n) = \Theta(n) + \Theta(n\log(n/k)) = \Theta(n\log(n/k))\]

    This is \(\Theta(n(\log n - \log k))\), which simplifies to \(\Theta(n\log(n/k))\).

Answer for (c): \(T_{\text{best}}(n, k) = \Theta(n\log(n/k))\) or \(\Theta(n\log n - n\log k)\)

Summary:

  • Worst case: \(\Theta(nk + n\log(n/k))\) — dominated by insertion sort if \(k\) is large
  • Best case: \(\Theta(n\log(n/k))\) — approaches pure merge sort efficiency when input is pre-sorted or \(k\) is small
  • Intuition: Setting \(k\) to a small constant (like 10) gives practical hybrid sort with \(\Theta(n\log n)\) complexity and low overhead
4.4. Solve \(T(n) = 2T(n/4) + 1\) Using Master Theorem (Lecture 3, Example 1)

Solve the recurrence relation and provide the asymptotic bound.

Click to see the solution

Key Concept: Identify parameters \(a\), \(b\), \(f(n)\) and apply the appropriate case of the Master Theorem.

  1. Identify parameters:
    • \(a = 2\) (two recursive calls)
    • \(b = 4\) (size divided by 4)
    • \(f(n) = 1\) (constant work for divide and combine)
  2. Compute the recursion cost: \[n^{\log_b a} = n^{\log_4 2} = n^{1/2} = \sqrt{n}\]
  3. Compare \(f(n)\) with \(n^{\log_4 2}\):
    • \(f(n) = 1\)
    • We need to check if \(1 = O(n^{1/2 - \epsilon})\) for some \(\epsilon > 0\)
    • Yes! Choose \(\epsilon = 1/2\). Then \(n^{1/2 - \epsilon} = n^0 = 1\), and \(1 = O(1)\)
  4. Apply Case 1: \[T(n) = \Theta(n^{\log_4 2}) = \Theta(\sqrt{n})\]

Answer: \(T(n) = \Theta(\sqrt{n})\)

4.5. Solve \(T(n) = 2T(n/4) + \sqrt{n}\) Using Master Theorem (Lecture 3, Example 2)
Click to see the solution

Key Concept: When \(f(n)\) matches \(n^{\log_b a}\) exactly (up to logarithmic factors), use Case 2.

  1. Identify parameters:
    • \(a = 2\)
    • \(b = 4\)
    • \(f(n) = \sqrt{n} = n^{1/2}\)
  2. Compute the recursion cost: \[n^{\log_4 2} = n^{1/2}\]
  3. Compare:
    • \(f(n) = n^{1/2}\)
    • \(n^{\log_4 2} = n^{1/2}\)
    • They match! Check if \(f(n) = \Theta(n^{1/2} \log^k n)\) for some \(k\)
    • Yes, with \(k = 0\): \(f(n) = \sqrt{n} = \Theta(n^{1/2} \log^0 n)\)
  4. Apply Case 2: \[T(n) = \Theta(n^{\log_4 2} \log^{0+1} n) = \Theta(\sqrt{n} \log n)\]

Answer: \(T(n) = \Theta(\sqrt{n} \log n)\)

4.6. Solve \(T(n) = 2T(n/4) + n\) Using Master Theorem (Lecture 3, Example 3)
Click to see the solution

Key Concept: When \(f(n)\) dominates \(n^{\log_b a}\), use Case 3 (if the regularity condition holds).

  1. Identify parameters:
    • \(a = 2\)
    • \(b = 4\)
    • \(f(n) = n\)
  2. Compute the recursion cost: \[n^{\log_4 2} = n^{1/2} = \sqrt{n}\]
  3. Compare:
    • \(f(n) = n = n^1\)
    • \(n^{\log_4 2} = n^{1/2}\)
    • \(n^1 > n^{1/2}\), so \(f(n)\) dominates. Check if \(f(n) = \Omega(n^{1/2 + \epsilon})\) for some \(\epsilon > 0\)
    • Yes, choose \(\epsilon = 1/2\): \(n = \Omega(n^{1/2 + 1/2}) = \Omega(n)\) ✓
  4. Verify regularity condition:
    • Need: \(a \cdot f(n/b) \le c \cdot f(n)\) for some \(c < 1\)
    • \(2 \cdot (n/4) \le c \cdot n\)
    • \(n/2 \le cn\)
    • Choose \(c = 1/2 < 1\) ✓
  5. Apply Case 3: \[T(n) = \Theta(f(n)) = \Theta(n)\]

Answer: \(T(n) = \Theta(n)\)

4.7. Trace Merge Sort Example (Lecture 3, Example 4)

Sort the array \([5, 2, 4, 6, 1, 3]\) using merge sort. Trace the divide and merge steps.

Click to see the solution

Key Concept: Recursively divide the array in half, then merge sorted subarrays.

  1. Initial array: \([5, 2, 4, 6, 1, 3]\)
  2. First divide (split in half):
    • Left: \([5, 2, 4]\)
    • Right: \([6, 1, 3]\)
  3. Recursively sort left \([5, 2, 4]\):
    • Divide: \([5]\) and \([2, 4]\)
    • Further divide \([2, 4]\): \([2]\) and \([4]\)
    • Merge \([2]\) and \([4]\): \([2, 4]\)
    • Merge \([5]\) and \([2, 4]\): \([2, 4, 5]\)
  4. Recursively sort right \([6, 1, 3]\):
    • Divide: \([6]\) and \([1, 3]\)
    • Further divide \([1, 3]\): \([1]\) and \([3]\)
    • Merge \([1]\) and \([3]\): \([1, 3]\)
    • Merge \([6]\) and \([1, 3]\): \([1, 3, 6]\)
  5. Merge the two sorted halves:
    • Left: \([2, 4, 5]\), Right: \([1, 3, 6]\)
    • Compare 2 and 1 → copy 1 → \([1]\)
    • Compare 2 and 3 → copy 2 → \([1, 2]\)
    • Compare 4 and 3 → copy 3 → \([1, 2, 3]\)
    • Compare 4 and 6 → copy 4 → \([1, 2, 3, 4]\)
    • Compare 5 and 6 → copy 5 → \([1, 2, 3, 4, 5]\)
    • Copy remaining 6 → \([1, 2, 3, 4, 5, 6]\)

Answer: Final sorted array: \([1, 2, 3, 4, 5, 6]\)

4.8. Trace Quicksort Partition Example (Lecture 3, Example 5)

Partition the array \([4, 9, 5, 1, 4, 7, 3, 6, 8, 2]\) using the last element (2) as the pivot.

Click to see the solution

Key Concept: Rearrange elements so those \(\le\) pivot are on the left, those \(>\) pivot are on the right.

  1. Initial array: \([4, 9, 5, 1, 4, 7, 3, 6, 8, 2]\)
    • Pivot \(x = 2\) (last element)
  2. Partitioning process:
    • Initialize \(i = -1\) (low partition boundary)
    • Scan \(j\) from 0 to 8 (excluding pivot at index 9)
    Step \(j\) \(A[j]\) Compare Action Array \(i\)
    1 0 4 \(4 > 2\) Skip \([4, 9, 5, 1, 4, 7, 3, 6, 8, 2]\) -1
    2 1 9 \(9 > 2\) Skip \([4, 9, 5, 1, 4, 7, 3, 6, 8, 2]\) -1
    3 2 5 \(5 > 2\) Skip \([4, 9, 5, 1, 4, 7, 3, 6, 8, 2]\) -1
    4 3 1 \(1 \le 2\) Swap \(A[0]\) and \(A[3]\) \([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\) 0
    5 4 4 \(4 > 2\) Skip \([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\) 0
    6 5 7 \(7 > 2\) Skip \([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\) 0
    7 6 3 \(3 > 2\) Skip \([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\) 0
    8 7 6 \(6 > 2\) Skip \([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\) 0
    9 8 8 \(8 > 2\) Skip \([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\) 0
  3. Place pivot in its final position:
    • Swap \(A[i+1]\) with \(A[9]\): Swap \(A[1]\) (value 9) with pivot 2
    • Result: \([1, 2, 5, 4, 4, 7, 3, 6, 8, 9]\)
  4. Interpretation:
    • Elements \(\le 2\): Left partition is \([1]\) (at index 0)
    • Pivot: 2 is now at index 1
    • Elements \(> 2\): Right partition is \([5, 4, 4, 7, 3, 6, 8, 9]\) (indices 2-9)

Answer: After partition with pivot 2: \([1, 2, 5, 4, 4, 7, 3, 6, 8, 9]\). Pivot is at index 1.

4.9. Find Maximum Subarray Using Divide and Conquer (Lecture 3, Example 6)

Find the maximum subarray of \([2, -1, 3, 4, 1, -5]\).

Click to see the solution

Key Concept: Divide the array, recursively find maximum subarrays in each half, and check for subarrays crossing the middle.

  1. Initial array: \([2, -1, 3, 4, 1, -5]\) (indices 1-6)
  2. First divide at midpoint \(m = 3\):
    • Left: \([2, -1, 3]\) (indices 1-3)
    • Right: \([4, 1, -5]\) (indices 4-6)
  3. Find maximum subarray in left half \([2, -1, 3]\):
    • Divide at \(m = 2\): \([2]\) and \([-1, 3]\)
    • Left \([2]\): max subarray is \([2]\) with sum 2
    • Right \([-1, 3]\):
      • Divide at \(m = 2\) (single element): max of \([-1]\) and \([3]\)
      • \([3]\) has sum 3
      • For crossing at \(m = 2\): best from left is \(-1\), best from right is \(3\), sum is \(-1 + 3 = 2\)
      • Max of right half: \([3]\) with sum 3
    • Compare: left \([2]\) (sum 2), right \([3]\) (sum 3), crossing \([-1, 3]\) (sum 2)
    • Max in left half: \([3]\) with sum 3
  4. Find maximum subarray in right half \([4, 1, -5]\):
    • Divide at \(m = 5\): \([4]\) and \([1, -5]\)
    • Left \([4]\): sum 4
    • Right \([1, -5]\):
      • Further divide: \([1]\) and \([-5]\)
      • Max of left: \([1]\) with sum 1
      • Max of right: \([-5]\) with sum -5 (better than nothing)
      • Crossing: \(1 + (-5) = -4\)
      • Max of right half: \([1]\) with sum 1
    • Compare: left \([4]\) (sum 4), right \([1]\) (sum 1), crossing \([4, 1]\) (sum 5)
    • Max in right half: \([4, 1]\) with sum 5
  5. Find maximum crossing subarray (at original midpoint \(m = 3\)):
    • Best sum extending left from index 3: \(3\) (just index 3)
    • Best sum extending right from index 4: \(4 + 1 = 5\) (indices 4-5)
    • Crossing sum: \(3 + 5 = 8\)
    • Crossing subarray: indices 3-5, which is \([3, 4, 1]\)
  6. Final comparison:
    • Left max: \([3]\) with sum 3
    • Right max: \([4, 1]\) with sum 5
    • Crossing max: \([3, 4, 1]\) with sum 8
    • Overall maximum: \([3, 4, 1]\) with sum 8 (indices 3-5)

Answer: Maximum subarray is \([3, 4, 1]\) with sum 8.

4.10. Analyze Merge Sort Time Complexity (Lecture 3, Example 7)

Given the merge sort recurrence \(T(n) = 2T(n/2) + \Theta(n)\), solve using the Master Theorem.

Click to see the solution

Key Concept: Merge sort is a classic example of Case 2 in the Master Theorem.

  1. Identify parameters:
    • \(a = 2\) (two recursive calls on two halves)
    • \(b = 2\) (each half is \(n/2\))
    • \(f(n) = \Theta(n)\) (merging takes linear time)
  2. Compute the recursion cost: \[n^{\log_b a} = n^{\log_2 2} = n^1 = n\]
  3. Compare \(f(n)\) with \(n^1\):
    • \(f(n) = \Theta(n)\)
    • \(n^{\log_2 2} = \Theta(n)\)
    • They match! Check if \(f(n) = \Theta(n^1 \cdot \log^k n)\)
    • Yes, with \(k = 0\)
  4. Apply Case 2: \[T(n) = \Theta(n^{\log_2 2} \cdot \log^{0+1} n) = \Theta(n \log n)\]
  5. Interpretation:
    • Work is distributed across \(\log n\) levels of recursion
    • Each level does \(\Theta(n)\) work (merging all arrays at that level)
    • Total: \(\log n\) levels × \(\Theta(n)\) work per level = \(\Theta(n \log n)\)

Answer: Time complexity of merge sort is \(\Theta(n \log n)\).

4.11. Analyze Quicksort Worst-Case Time Complexity (Lecture 3, Example 8)

Show that quicksort has worst-case complexity \(\Theta(n^2)\) by setting up and solving the recurrence.

Click to see the solution

Key Concept: The worst case occurs when the pivot is always at one end, creating unbalanced partitions.

  1. Worst-case recurrence:
    • When the pivot is the smallest (or largest) element, one partition has \(n-1\) elements and the other has 0.
    • Recurrence: \(T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + \Theta(n)\)
  2. Expand the recurrence: \[T(n) \le T(n-1) + cn\] \[\le T(n-2) + c(n-1) + cn\] \[\le T(n-3) + c(n-2) + c(n-1) + cn\] \[\vdots\] \[\le T(1) + c \cdot 2 + c \cdot 3 + \cdots + cn\]
  3. Sum the costs: \[T(n) \le T(1) + c \sum_{i=2}^{n} i = c \left( \frac{n(n+1)}{2} - 1 \right)\] \[= c \cdot \frac{n^2 + n - 2}{2} = \Theta(n^2)\]
  4. Master Theorem verification:
    • Parameters: \(a = 1\), \(b = 1\), but this is not in standard form \(b > 1\)
    • The Master Theorem doesn’t directly apply
    • But expanding the recurrence shows \(T(n) = \Theta(n^2)\)

Answer: Worst-case time complexity of quicksort is \(\Theta(n^2)\).

4.12. Master Theorem Practice Problems (Lecture 3, Task 1)

Solve each recurrence using the Master Theorem. State which case applies and justify.

  1. \(T(n) = 3T(n/2) + n^2\)
  2. \(T(n) = 4T(n/2) + n^2\)
  3. \(T(n) = T(n/2) + 2^n\)
  4. \(T(n) = 16T(n/4) + n\)
Click to see the solution

(1) \(T(n) = 3T(n/2) + n^2\):

  • \(a = 3\), \(b = 2\), \(f(n) = n^2\)
  • \(n^{\log_2 3} = n^{\log_2 3} \approx n^{1.585}\)
  • Compare \(n^2\) with \(n^{1.585}\): \(n^2 > n^{1.585}\), so \(f(n)\) dominates
  • Check Case 3: \(f(n) = \Omega(n^{\log_2 3 + \epsilon})\) with \(\epsilon \approx 0.415\) ✓
  • Regularity: \(3 \cdot (n/2)^2 = 3n^2/4 \le cn^2\) with \(c = 3/4 < 1\) ✓
  • Answer: \(T(n) = \Theta(n^2)\) (Case 3)

(2) \(T(n) = 4T(n/2) + n^2\):

  • \(a = 4\), \(b = 2\), \(f(n) = n^2\)
  • \(n^{\log_2 4} = n^2\)
  • Compare \(n^2\) with \(n^2\): They match!
  • Check Case 2: \(f(n) = \Theta(n^2 \log^k n)\) with \(k = 0\) ✓
  • Answer: \(T(n) = \Theta(n^2 \log n)\) (Case 2)

(3) \(T(n) = T(n/2) + 2^n\):

  • \(a = 1\), \(b = 2\), \(f(n) = 2^n\)
  • \(n^{\log_2 1} = n^0 = 1\)
  • Compare \(2^n\) with \(1\): \(2^n\) dominates
  • Check Case 3: \(f(n) = \Omega(1 + \epsilon)\) for any \(\epsilon > 0\) ✓
  • Regularity: \(1 \cdot 2^{n/2} \le c \cdot 2^n\), i.e., \(2^{n/2} \le c \cdot 2^n\)
    • This holds with \(c = 1/2\) since \(2^{n/2} = \sqrt{2^n} \le (1/2) \cdot 2^n\) for \(n \ge 2\) ✓
  • Answer: \(T(n) = \Theta(2^n)\) (Case 3)

(4) \(T(n) = 16T(n/4) + n\):

  • \(a = 16\), \(b = 4\), \(f(n) = n\)
  • \(n^{\log_4 16} = n^{\log_4 16} = n^2\) (since \(4^2 = 16\))
  • Compare \(n\) with \(n^2\): \(n^2\) dominates (recursion is larger)
  • Check Case 1: \(f(n) = O(n^{2 - \epsilon})\) with \(\epsilon = 1\) ✓
  • Answer: \(T(n) = \Theta(n^2)\) (Case 1)