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

I. Orientation — Foundations of Algorithm Analysis

Algorithm analysis predicts the resources required by an algorithm as input size grows. Divide-and-conquer algorithms solve a problem by dividing it into smaller subproblems, solving them recursively, and combining their results.

• Input size: Denoted by (n), it measures the problem scale—for example, the number of array elements or matrix dimension.
• Cost model: Primitive operations such as comparisons, assignments, and arithmetic operations are treated as constant-time operations.
• Asymptotic focus: Growth rates are studied for large (n), ignoring constant factors and lower-order terms.
• Cases of analysis:
  • Best case: Minimum cost among inputs of size (n).
  • Average case: Expected cost under an assumed input distribution.
  • Worst case: Maximum cost among inputs of size (n).
• Divide-and-conquer structure:
  • Divide: Split the input into smaller subproblems.
  • Conquer: Solve each subproblem, usually recursively.
  • Combine: Construct the original solution from subproblem solutions.
• Recurrence model: A divide-and-conquer running time is commonly expressed as (T(n)=aT(n/b)+f(n)), where (a) is the number of subproblems, (n/b) is each subproblem’s size, and (f(n)) is nonrecursive work.

II. Complexity Measures — Resource Growth

A. Time and Space Complexity

Time complexity measures operation growth, while space complexity measures memory growth as a function of input size.

• Asymptotic upper bound: (T(n)=O(g(n))) when constants (c>0) and (n_0) exist such that (0\le T(n)\le cg(n)) for every (n\ge n_0).
• Asymptotic lower bound: (T(n)=\Omega(g(n))) when (T(n)\ge cg(n)) for sufficiently large (n).
• Tight bound: (T(n)=\Theta(g(n))) when (T(n)) is both (O(g(n))) and (\Omega(g(n))).
• Common growth order:

1 < log n < n < n log n < n² < n³ < 2ⁿ < n!

• Space components: Total space consists of input space and auxiliary space. An in-place algorithm normally uses (O(1)) auxiliary space, whereas merge sort requires (O(n)) temporary array space.
• Recursion space: A recursive call stack contributes one frame per active call. A recursion depth of (\log n) therefore requires (O(\log n)) stack space.
• Simplification: If (T(n)=3n^2+7n+4), the dominant term gives (T(n)=\Theta(n^2)).

III. Sorting Analysis — Incremental and Divide-and-Conquer Sorting

A. Complexity Analysis of Insertion Sort and Merge Sort

Insertion sort builds a sorted prefix, whereas merge sort recursively divides and merges the input.

1. Insertion sort
   • Operation: At iteration (j), the key (A[j]) moves left until it reaches its correct position in (A[0\ldots j]).
   • Best case: An already sorted array needs one comparison per iteration, giving (\Theta(n)) time.
   • Worst case: A reverse-sorted array produces

1 + 2 + ··· + (n − 1) = n(n − 1)/2 = Θ(n²)

• Resources: It uses (O(1)) auxiliary space, is stable when equal keys are not moved past one another, and performs well on small or nearly sorted inputs.

2. Merge sort
   • Recurrence: Two half-sized recursive sorts and a linear merge give

T(n) = 2T(n/2) + Θ(n),  T(1) = Θ(1)

• Complexity: Each of (\log_2 n) levels performs (\Theta(n)) work, so all input arrangements take (\Theta(n\log n)) time.
• Resources: Array-based merging uses (\Theta(n)) auxiliary space plus (\Theta(\log n)) recursion depth; merge sort is stable when ties are taken from the left subarray first.
• Contrast: Insertion sort avoids temporary arrays but is quadratic in the worst case; merge sort guarantees (n\log n) time at the cost of extra memory.

IV. Forms of Analysis — Loops and Recursion

A. Analysis of Iterative Algorithms

Iterative analysis counts loop executions and combines the costs of sequential or nested statements.

• Single loop: A loop from (1) through (n), with constant work per iteration, costs (\Theta(n)).
• Sequential loops: Costs are added; (\Theta(n)+\Theta(n^2)=\Theta(n^2)).
• Nested loops: Dependent iteration counts are summed rather than automatically multiplied.

for i = 1 to n
    for j = 1 to i
        operation

• Concrete count: The operation executes (\sum_{i=1}^{n}i=n(n+1)/2), hence the running time is (\Theta(n^2)).
• Geometric progression: If a loop repeatedly doubles (i), then after (k) iterations (i=2^k). The stopping condition (2^k\ge n) gives (k=\lceil\log_2 n\rceil).
• Amortized caution: One expensive iteration does not necessarily make every iteration expensive; total cost over an operation sequence may provide a tighter bound.

B. Analysis of Recursive Algorithms

Recursive analysis expresses total cost as a recurrence containing subproblem costs and local work.

• Construction: Identify the base-case cost, number of recursive calls, size reduction, and work outside recursion.
• Linear recursion: The recurrence

T(n) = T(n − 1) + Θ(1)

expands to (\Theta(n)), as in a recursive traversal of (n) array elements.

• Binary recursion: (T(n)=2T(n/2)+\Theta(1)) has (\Theta(n)) total calls because the recursion tree contains approximately (2n-1) nodes.
• Stack usage: The longest active path determines stack space, not the total number of calls. Balanced halving gives depth (\Theta(\log n)).
• Termination: Every call must move toward a base case; otherwise neither time nor space complexity is bounded.

V. Recurrence-Solving Techniques — Asymptotic Proof Methods

A. Substitution Method

The substitution method guesses an asymptotic bound and proves it by mathematical induction.

• Procedure: Guess the form, assume it holds for smaller inputs, substitute the hypothesis, and verify constants and the base case.
• Upper-bound proof: For (T(n)=2T(n/2)+n), guess (T(n)\le cn\log_2 n). Substitution gives

T(n) ≤ 2[c(n/2)log₂(n/2)] + n
     = cn log₂n − cn + n
     ≤ cn log₂n

when (c\ge1).

• Conclusion: A corresponding lower-bound proof establishes (T(n)=\Theta(n\log n)).
• Limitation: A poor guess cannot be proved; lower-order corrections may be needed when induction leaves an uncompensated term.

B. Recursion Tree Method

A recursion tree represents each recursive call as a node and sums work across levels.

• Level cost: For (T(n)=2T(n/2)+n), level (i) has (2^i) nodes, each performing (n/2^i) work, so its total is (n).
• Height: Halving continues until (n/2^h=1), yielding (h=\log_2 n).
• Total: There are (\log_2 n) internal levels of cost (n), plus (\Theta(n)) leaf cost:

T(n) = n log₂n + Θ(n) = Θ(n log n)

• Use: The method exposes whether root, leaves, or all levels dominate, and often guides a substitution-method proof.

C. Master Method

The Master Method gives direct bounds for recurrences of the form (T(n)=aT(n/b)+f(n)), where (a\ge1), (b>1), and (f(n)) is asymptotically positive.

• Benchmark: Compare (f(n)) with (n^{\log_b a}), the total polynomial contribution of recursive leaves.
• Case 1: If (f(n)=O(n^{\log_ba-\varepsilon})) for some (\varepsilon>0), then

T(n) = Θ(n^(log_b a))

• Case 2: If (f(n)=\Theta(n^{\log_ba}\log^k n)) for (k\ge0), then (T(n)=\Theta(n^{\log_ba}\log^{k+1}n)).
• Case 3: If (f(n)=\Omega(n^{\log_ba+\varepsilon})) and (af(n/b)\le cf(n)) for some (c<1), then (T(n)=\Theta(f(n))).
• Limitation: The basic method does not directly handle unequal subproblem sizes, such as (T(n)=T(n/3)+T(2n/3)+n).

VI. Fast Matrix Products — Divide-and-Conquer Improvement

A. Strassen's Matrix Multiplication

Strassen’s algorithm multiplies matrices using seven recursive multiplications instead of the eight required by ordinary block multiplication.

• Partition: Each (n\times n) matrix is divided into four ((n/2)\times(n/2)) blocks.
• Key reduction: Carefully chosen sums and differences form seven products (M_1,\ldots,M_7), from which the four result blocks are reconstructed.
• Recurrence:

T(n) = 7T(n/2) + Θ(n²)

• Complexity: Since (\log_2 7\approx2.807), the Master Method gives (\Theta(n^{2.807})), improving on conventional (\Theta(n^3)) multiplication.
• Practical limitations: Additional additions, temporary matrices, numerical error, and implementation overhead make ordinary multiplication preferable below a chosen threshold.
• Input handling: Non-power-of-two dimensions may be padded with zero rows and columns without changing the represented product.

VII. Selection Concepts — Ranked Elements

A. Order Statistics

The (k)-th order statistic is the element occupying position (k) when (n) elements are arranged in nondecreasing order.

• Ranks: The first order statistic is the minimum, the (n)-th is the maximum, and a median has a central rank.
• Duplicates: Rank counts positions, not distinct values; in ([2,2,5,9]), the second-smallest element is (2).
• Sorting approach: Sorting followed by indexing takes (O(n\log n)) time, although only one ranked element is required.
• Selection lower bound: Finding the minimum or maximum requires at least (n-1) comparisons, establishing an (\Omega(n)) comparison bound.
• Linear selection: Partition-based randomized selection has expected (\Theta(n)) time; median-of-medians supports deterministic worst-case (\Theta(n)).

VIII. Partition-Based Selection — Locating a Required Rank

A. Quick Select

Quick Select uses Quick Sort’s partition operation but recursively processes only the side containing the desired rank.

• Partition result: After partitioning around pivot (p), elements smaller than (p) precede it and larger elements follow it; (p) reaches its final sorted position.
• Pseudocode:

QUICKSELECT(A, left, right, index)
    q = PARTITION(A, left, right)
    if q = index: return A[q]
    if index < q: return QUICKSELECT(A, left, q − 1, index)
    return QUICKSELECT(A, q + 1, right, index)

• Symbols: (A) is the array, left and right delimit the active region, index is the zero-based target position, and (q) is the pivot’s final index.
• Complexity: Balanced partitions give (T(n)=T(n/2)+\Theta(n)=\Theta(n)); repeatedly choosing an extreme pivot gives (\Theta(n^2)).
• Expected performance: Random pivot selection produces expected (\Theta(n)) time and typically modifies the array in place.

B. k-th Smallest Element

The (k)-th smallest element has one-based rank (k) in ascending order.

• Index conversion: For zero-based arrays, the target index is (k-1), where (1\le k\le n).
• Example: In ([7,2,9,4,1]), ascending order is ([1,2,4,7,9]); the third-smallest element is (4).
• Quick Select use: Partitioning discards the side that cannot contain index (k-1), avoiding complete sorting.
• Boundary cases: (k=1) requests the minimum, while (k=n) requests the maximum.

C. k-th Largest Element

The (k)-th largest element has rank (k) when values are ordered from largest to smallest.

• Rank conversion: In ascending zero-based order, its target index is (n-k).
• Example: In ([7,2,9,4,1]), the second-largest element is at index (5-2=3) in ([1,2,4,7,9]), giving (7).
• Equivalence: The (k)-th largest is the ((n-k+1))-th smallest under one-based ranking.
• Alternatives: A min-heap of size (k) uses (O(n\log k)) time and (O(k)) space, which is useful for streaming data where in-place partitioning is unavailable.