Unit 2: Divide and Conquer - Subjective Questions

Divide and conquer is an algorithm-design technique in which a problem is divided into smaller subproblems of the same type, the subproblems are solved, and their solutions are combined.

The three fundamental steps are:

• Divide: Split the original problem into smaller subproblems.
• Conquer: Solve each subproblem recursively. If a subproblem is sufficiently small, solve it directly as a base case.
• Combine: Merge the solutions of the subproblems to obtain the solution to the original problem.

Example—merge sort:

• Divide an array into two halves.
• Recursively sort both halves.
• Merge the two sorted halves.

For an input of size , its recurrence is

which gives .

A divide-and-conquer algorithm generally follows this structure:

1. If the input is small enough, solve it directly.
2. Divide an input of size into subproblems.
3. Recursively solve each subproblem of size approximately .
4. Combine the resulting solutions.

Its standard recurrence is

where:

• is the number of recursive subproblems.
• is the size of each subproblem.
• is the cost of dividing the problem and combining the solutions.
• is a typical base case.

The total running time depends on the relationship between and , as characterized by the Master Theorem.

For the recurrence

where , , and is asymptotically positive, compare with .

• Case 1: If for some , then
  
• Case 2: If for some , then
  
• Case 3: If for some , and the regularity condition holds for some , then
  

The theorem determines whether recursive work, equal work across levels, or divide-and-combine work dominates the running time.

The two strategies differ mainly in the number and size of recursive subproblems.

• Divide and conquer:

  • Divides a problem into multiple smaller subproblems.
  • Usually solves all subproblems recursively.
  • Combines their results.
  • Typical recurrence: , where .
  • Examples: merge sort and quick sort.

• Decrease and conquer:

  • Reduces the problem to one smaller subproblem.
  • Extends the smaller solution to solve the original problem.
  • Typical recurrence: or .
  • Examples: insertion sort and binary search.

Binary search is often described as divide and conquer, but more precisely it is decrease-by-a-constant-factor because only one half is recursively processed.

Binary search locates a target in a sorted array by repeatedly comparing the target with the middle element.

Procedure:

• Set low to the first index and high to the last index.
• Compute mid as .
• If the middle element equals the target, return its index.
• If the target is smaller, continue in the left half.
• Otherwise, continue in the right half.
• Report failure when .

Each comparison reduces the search interval from elements to at most . Thus,

After reductions, , so . Therefore:

• Best case:
• Worst and average cases:
• Iterative auxiliary space:
• Recursive auxiliary space:

Using zero-based indices:

• Initially, and .
• First middle index:
  
  The middle value is . Since , set .
• Second middle index:
  
  The middle value is . Since , set .
• Third middle index:
  
  The middle value is , so the search succeeds.

Thus, the key is found at index , or at position when positions are numbered from one. The search requires three comparisons.

Both implementations repeatedly halve a sorted search interval and therefore have the same asymptotic running time.

• Iterative binary search:

  • Uses a loop to update low and high.
  • Runs in time.
  • Uses auxiliary space.
  • Avoids function-call overhead.

• Recursive binary search:

  • Calls itself on either the left or right half.
  • Runs in time.
  • Uses stack space in the worst case.
  • Expresses the recursive structure more directly.

The iterative version is generally more space-efficient. In both versions, the input must be sorted, and the safe midpoint formula is

which avoids the possible overflow of .

Merge sort is a divide-and-conquer sorting algorithm.

Algorithm:

• Divide: Split the array into two approximately equal halves.
• Conquer: Recursively sort each half.
• Combine: Merge the two sorted halves into one sorted array.

The merge operation maintains pointers to the first unprocessed elements of both sorted halves. It repeatedly copies the smaller element into a temporary array. When one half is exhausted, all remaining elements from the other half are copied.

Merging two lists containing a total of elements takes time. The recurrence is

so merge sort runs in time in the best, average, and worst cases. The conventional array implementation requires auxiliary space and is stable when equal elements from the left half are selected first.

Merge sort satisfies

with .

In the recursion tree:

• Level has one problem of size , so merge work is .
• Level has two problems of size , giving total work .
• Level has problems of size , giving
  
• Recursion stops when , so the tree has non-leaf levels.
• The leaves contribute total base-case work.

Therefore,

The result is independent of the initial order of the elements because merge sort always performs the same pattern of divisions and linear merges.

Properties of merge sort:

• Stability: Merge sort is stable if the merge procedure selects an element from the left half before an equal element from the right half.
• Time complexity: It takes time in the best, average, and worst cases.
• Array space complexity: A standard implementation uses auxiliary storage, plus recursive stack space of .
• Linked-list space: Linked lists can be merged mainly by changing pointers, reducing the need for a temporary array.

Advantages:

• Predictable worst-case performance.
• Suitable for linked lists and external sorting.
• Naturally supports parallel processing.

Limitations:

• Requires additional memory for arrays.
• Often has larger constant overhead than an efficient in-place quick sort.
• Does not adapt automatically to already sorted input unless specifically optimized.

Quick sort is a divide-and-conquer sorting algorithm centered on a selected pivot.

Steps:

• Choose a pivot from the current subarray.
• Partition the subarray so that elements smaller than or equal to the pivot are placed on one side and larger elements on the other side, according to the chosen partition scheme.
• Place the pivot in its final sorted position when the scheme guarantees this directly.
• Recursively sort the two resulting subarrays.

Partitioning takes time for a subarray of size . If the pivot creates subarrays of sizes and , then

Balanced partitions produce time, while repeatedly choosing an extreme element produces time. Quick sort is commonly implemented in place but is not stable in its standard form.

Lomuto partition scheme:

• Commonly chooses the last element as the pivot.
• Maintains a boundary for elements not greater than the pivot.
• Scans the subarray with one main scan index.
• Places the pivot at its final index after the scan.
• Is simple to understand but often performs more swaps.

Hoare partition scheme:

• Commonly chooses the first or middle element as the pivot value.
• Uses two indices moving inward from opposite ends.
• Swaps elements found on the wrong sides.
• Usually performs fewer swaps than Lomuto partitioning.
• Returns a split position; the returned index is not necessarily the pivot's final position.

The recursive bounds must match the selected scheme. Treating Hoare's returned split as if it were Lomuto's final pivot index can lead to incorrect recursion or nontermination.

Best case: The pivot divides the array into two nearly equal parts. The recurrence is

There are levels, and each level performs partition work. Hence,

Worst case: The pivot is repeatedly the smallest or largest element, producing subproblems of sizes and . Then

Expanding the recurrence gives

This worst case may occur when the first or last element is always selected as pivot for already sorted or reverse-sorted data. Random pivot selection makes such consistently bad partitions unlikely, yielding expected time .

Pivot selection controls the sizes of the partitions and therefore affects quick sort's recursion depth and running time.

• First or last element: Easy to implement, but can produce highly unbalanced partitions on sorted or nearly sorted inputs.
• Random pivot: Selects a uniformly random position. It reduces dependence on input order and gives expected running time , although the theoretical worst case remains .
• Median-of-three: Uses the median of the first, middle, and last elements. It often avoids poor pivots on common input patterns and can reduce constant factors.

The ideal pivot is the true median because it creates balanced partitions, but finding the exact median may add excessive overhead. Practical implementations therefore use inexpensive approximations or randomization.

Merge sort:

• Best, average, and worst time: .
• Standard array implementation uses auxiliary space.
• Stable when implemented appropriately.
• Well suited to linked lists, external sorting, and applications requiring guaranteed worst-case performance.

Quick sort:

• Best and expected time: .
• Worst time: .
• Usually sorts arrays in place, with expected stack space ; an unbalanced recursion can use stack space.
• Standard implementations are not stable.
• Often faster for in-memory arrays because of good cache locality and low constant factors.

Thus, merge sort offers predictability and stability, whereas quick sort often offers better practical in-memory performance and lower auxiliary array storage.

Let two -digit integers in base be split around digits:

Here, and are the high halves, while and are the low halves. Their product is

A direct divide-and-conquer method recursively computes four half-size products:

Shifting by powers of and adding results take time. Therefore,

By the Master Theorem,

Thus, this straightforward recursive method has the same asymptotic complexity as traditional grade-school multiplication, although it reveals the structure needed for faster methods.

Split the two integers as

The ordinary expansion is

Karatsuba avoids computing and separately. Compute only

Since

the middle term is

Therefore,

Only three recursive half-size multiplications are required. Additions, subtractions, and shifts cost , giving

By the Master Theorem,

This is asymptotically faster than the grade-school method.

Split each number after two decimal digits, so :

Let , , , and . Compute:

The middle coefficient is

Recombine the terms:

Therefore,

• Grade-school multiplication: Multiplies every digit of one operand by every digit of the other. For two -digit integers, its time complexity is .

• Four-product divide-and-conquer: Splits each operand into halves and recursively computes , , , and . Its recurrence is
  
  so its complexity is also .

• Karatsuba multiplication: Replaces four half-size multiplications with three by deriving the middle term from . Its recurrence is
  
  giving .

Karatsuba is asymptotically faster, but for small inputs its recursive calls and extra additions can make it slower. Practical libraries therefore switch to grade-school multiplication below a chosen threshold.

Important implementation issues include:

• Representation: Large integers may be stored as arrays of digits or machine-word blocks in a base such as or .
• Splitting: Operands must be separated into high and low blocks efficiently, with unequal lengths and leading zeros handled correctly.
• Carry and borrow: Additions and subtractions require proper propagation across blocks.
• Shifting: Multiplication by should be implemented as a block shift rather than repeated arithmetic multiplication.
• Sign handling: The algorithm must account for negative operands and possibly negative intermediate values such as .
• Base cases: Recursion should stop below a threshold and use grade-school multiplication because it has smaller constant overhead.
• Memory management: Temporary arrays should be reused where possible to reduce allocation cost.

Although Karatsuba has better asymptotic complexity, these engineering choices determine its actual crossover point and practical performance.