Divide and Conquer

This chapter introduces the fundamental Divide and Conquer paradigm, a cornerstone of efficient algorithm design. We explore its principles, common applications, and the critical role it plays in analyzing the time complexity of many advanced algorithms. Mastery of this concept is essential for success in algorithmic analysis and design sections of the examination.

---

Chapter Contents

|

| Topic |

|---|-------| | 1 | Core Concept |

---

We begin with Core Concept.

Part 1: Core Concept

Divide and Conquer is a fundamental algorithmic paradigm that recursively breaks down a problem into two or more subproblems of the same or related type, until these become simple enough to be solved directly. The solutions to the subproblems are then combined to give a solution to the original problem.

---

Core Concepts

1. The Divide and Conquer Paradigm

We define the Divide and Conquer paradigm by three steps:

Divide: Break the problem into smaller subproblems.

Conquer: Solve each subproblem recursively. If a subproblem is small enough, solve it directly (base case).

Combine: Combine the solutions to the subproblems to obtain the solution for the original problem.

Worked Example: Finding the maximum element in an array using Divide and Conquer.

Consider an array $A$ of $n$ elements. We want to find the maximum element.

```python
def find_max(A, low, high):
if low == high:

Base case: single element

return A[low] mid = (low + high) // 2

Conquer: Recursively find max in left and right halves

max_left = find_max(A, low, mid) max_right = find_max(A, mid + 1, high)

Combine: Return the larger of the two maximums

return max(max_left, max_right) ```

Step 1: Initial call with $A = [3, 8, 1, 9, 4, 7]$, `low = 0`, `high = 5`.

> `find_max([3, 8, 1, 9, 4, 7], 0, 5)`
> `mid = (0 + 5) // 2 = 2`

Step 2: Recursive calls for left and right halves.

> `max_left = find_max([3, 8, 1, 9, 4, 7], 0, 2)` (subarray `[3, 8, 1]`)
> `mid = (0 + 2) // 2 = 1`
> `max_left_left = find_max([3, 8, 1], 0, 1)` (subarray `[3, 8]`)
> `mid = (0 + 1) // 2 = 0`
> `max_left_left_left = find_max([3, 8], 0, 0)` -> Returns `3`
> `max_left_left_right = find_max([3, 8], 1, 1)` -> Returns `8`
> `max(3, 8)` -> Returns `8` for `find_max([3, 8], 0, 1)`
> `max_left_right = find_max([3, 8, 1], 2, 2)` (subarray `[1]`) -> Returns `1`
> `max(8, 1)` -> Returns `8` for `find_max([3, 8, 1], 0, 2)`

Step 3: Continue with the right half of the original array.

> `max_right = find_max([3, 8, 1, 9, 4, 7], 3, 5)` (subarray `[9, 4, 7]`)
> `mid = (3 + 5) // 2 = 4`
> `max_right_left = find_max([9, 4, 7], 3, 4)` (subarray `[9, 4]`)
> `mid = (3 + 4) // 2 = 3`
> `max_right_left_left = find_max([9, 4], 3, 3)` -> Returns `9`
> `max_right_left_right = find_max([9, 4], 4, 4)` -> Returns `4`
> `max(9, 4)` -> Returns `9` for `find_max([9, 4], 3, 4)`
> `max_right_right = find_max([9, 4, 7], 5, 5)` (subarray `[7]`) -> Returns `7`
> `max(9, 7)` -> Returns `9` for `find_max([9, 4, 7], 3, 5)`

Step 4: Combine the results from the initial recursive calls.

> `max(max_left, max_right) = max(8, 9)` -> Returns `9`

Answer: The maximum element is $9$.

:::question type="NAT" question="Consider the function `SUM(A, low, high)` which computes the sum of elements in an array segment.
```python
def SUM(A, low, high):
if low == high:
return A[low]
mid = (low + high) // 2
return SUM(A, low, mid) + SUM(A, mid + 1, high)
```
If $A = [10, 20, 30, 40, 50]$ and we call `SUM(A, 0, 4)`, what is the final return value?" answer="150" hint="Trace the recursive calls and sums. The function performs a divide and conquer sum." solution="Step 1: Initial call `SUM(A, 0, 4)`
> `mid = (0+4)//2 = 2`
> `return SUM(A, 0, 2) + SUM(A, 3, 4)`

Step 2: Evaluate `SUM(A, 0, 2)` (subarray `[10, 20, 30]`)
> `mid = (0+2)//2 = 1`
> `return SUM(A, 0, 1) + SUM(A, 2, 2)`
> `SUM(A, 2, 2)` returns `A[2] = 30`
> `SUM(A, 0, 1)` (subarray `[10, 20]`)
> `mid = (0+1)//2 = 0`
> `return SUM(A, 0, 0) + SUM(A, 1, 1)`
> `SUM(A, 0, 0)` returns `A[0] = 10`
> `SUM(A, 1, 1)` returns `A[1] = 20`
> `10 + 20 = 30` for `SUM(A, 0, 1)`
> `30 + 30 = 60` for `SUM(A, 0, 2)`

Step 3: Evaluate `SUM(A, 3, 4)` (subarray `[40, 50]`)
> `mid = (3+4)//2 = 3`
> `return SUM(A, 3, 3) + SUM(A, 4, 4)`
> `SUM(A, 3, 3)` returns `A[3] = 40`
> `SUM(A, 4, 4)` returns `A[4] = 50`
> `40 + 50 = 90` for `SUM(A, 3, 4)`

Step 4: Combine the results from initial call.
> `60 + 90 = 150`

The final return value is $150$."
:::

---

2. Recurrence Relations

We use recurrence relations to describe the running time of recursive algorithms, particularly those following the Divide and Conquer paradigm. A recurrence relation expresses the running time $T(n)$ for a problem of size $n$ in terms of the running time on smaller inputs.

Worked Example: Setting up the recurrence for Merge Sort.

Merge Sort divides an array of size $n$ into two subarrays of size $n/2$, recursively sorts them, and then merges the sorted subarrays.

Step 1: Analyze the divide step.
> Dividing the array into two halves takes $O(1)$ time.

Step 2: Analyze the conquer step.
> We recursively solve two subproblems, each of size $n/2$. This contributes $2T(n/2)$ to the running time.

Step 3: Analyze the combine step.
> Merging two sorted subarrays of total size $n$ takes $O(n)$ time.

Step 4: Formulate the recurrence relation.
> Combining these, the recurrence for Merge Sort is:
>

> The base case is $T(1) = O(1)$, as an array of one element is already sorted.

Answer: The recurrence relation for Merge Sort is $T(n) = 2T(n/2) + O(n)$.

:::question type="MCQ" question="What is the recurrence relation for the worst-case running time of a Binary Search algorithm on an array of size $n$?" options=["$T(n) = T(n-1) + O(1)$","$T(n) = T(n/2) + O(1)$","$T(n) = 2T(n/2) + O(1)$","$T(n) = T(n/2) + O(n)$"] answer="$T(n) = T(n/2) + O(1)$" hint="Binary Search divides the problem into one subproblem of half the size and performs constant work." solution="Step 1: Analyze Binary Search operations.
Binary Search compares the target element with the middle element of the array.
If they match, the search is complete ($O(1)$).
If the target is smaller, the search continues in the left half.
If the target is larger, the search continues in the right half.

Step 2: Formulate recurrence.
In the worst case, we make one comparison ($O(1)$) and then recurse on one subproblem of size $n/2$.
Therefore, the recurrence relation is $T(n) = T(n/2) + O(1)$.
The base case is $T(1) = O(1)$.

The correct option is $T(n) = T(n/2) + O(1)$."
:::

---

3. Master Theorem

The Master Theorem provides a cookbook method for solving recurrence relations of the form $T(n) = aT(n/b) + f(n)$, which commonly arise from Divide and Conquer algorithms.

Worked Example: Apply the Master Theorem to solve $T(n) = 4T(n/2) + n$.

Step 1: Identify parameters $a, b, f(n)$.

> From the recurrence $T(n) = 4T(n/2) + n$, we have:
> $a = 4$
> $b = 2$
> $f(n) = n$

Step 2: Calculate $n^{\log_b a}$.

>

Step 3: Compare $f(n)$ with $n^{\log_b a}$.

> We compare $f(n) = n$ with $n^{\log_b a} = n^2$.
> Since $n = O(n^{2 - \epsilon})$ for any $\epsilon$ such that $0 < \epsilon \le 1$ (e.g., $\epsilon=1$, $n = O(n^1)$), this falls under Case 1 of the Master Theorem.

Step 4: Determine the asymptotic bound.

> According to Case 1, if $f(n) = O(n^{\log_b a - \epsilon})$, then $T(n) = \Theta(n^{\log_b a})$.
> Therefore, $T(n) = \Theta(n^2)$.

Answer: The solution to the recurrence $T(n) = 4T(n/2) + n$ is $T(n) = \Theta(n^2)$.

:::question type="MCQ" question="What is the asymptotic solution to the recurrence relation $T(n) = 3T(n/3) + n \log n$ using the Master Theorem?" options=["$\Theta(n)$","$\Theta(n \log n)$","$\Theta(n \log^2 n)$","$\Theta(n^{1.5})$"] answer="$\Theta(n \log^2 n)$" hint="Identify $a, b, f(n)$, calculate $n^{\log_b a}$, then compare $f(n)$ with $n^{\log_b a}$ to determine the case." solution="Step 1: Identify parameters $a, b, f(n)$.
> From $T(n) = 3T(n/3) + n \log n$:
> $a = 3$
> $b = 3$
> $f(n) = n \log n$

Step 2: Calculate $n^{\log_b a}$.
>

Step 3: Compare $f(n)$ with $n^{\log_b a}$.
> We compare $f(n) = n \log n$ with $n^{\log_b a} = n$.
> We observe that $f(n) = n \log n = \Theta(n \log n)$. This is asymptotically larger than $n$ but not polynomially larger ($n \log n$ is not $\Omega(n^{1+\epsilon})$).
> This situation is a variant of Case 2 where $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k \ge 0$. Here, $k=1$.
> The standard Master Theorem (Case 2) applies when $f(n) = \Theta(n^{\log_b a})$, leading to $T(n) = \Theta(n^{\log_b a} \log n)$.
> If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k \ge 0$, then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
> Here, $n^{\log_b a} = n$ and $f(n) = n \log n = \Theta(n \log^1 n)$, so $k=1$.
> Thus, $T(n) = \Theta(n \log^{1+1} n) = \Theta(n \log^2 n)$.

The correct option is $\Theta(n \log^2 n)$."
:::

---

4. Merge Sort

Merge Sort is a stable, comparison-based sorting algorithm that exemplifies the Divide and Conquer paradigm. It has a worst-case time complexity of $O(n \log n)$.

Worked Example: Sorting an array using Merge Sort.

Sort the array $A = [38, 27, 43, 3, 9, 82, 10]$ using Merge Sort.

Step 1: Divide the array recursively until single-element arrays are formed.

> `[38, 27, 43, 3, 9, 82, 10]`
> Divide: `[38, 27, 43, 3]` | `[9, 82, 10]`
> Divide: `[38, 27]` | `[43, 3]` | `[9, 82]` | `[10]`
> Divide: `[38]` | `[27]` | `[43]` | `[3]` | `[9]` | `[82]` | `[10]`

Step 2: Conquer by merging sorted subarrays.

> Merge: `[27, 38]` | `[3, 43]` | `[9, 82]` | `[10]`
> (From `[38]` and `[27]`, we get `[27, 38]`. From `[43]` and `[3]`, we get `[3, 43]`. From `[9]` and `[82]`, we get `[9, 82]`. `[10]` remains.)

Step 3: Continue merging.

> Merge: `[3, 27, 38, 43]` | `[9, 10, 82]`
> (From `[27, 38]` and `[3, 43]`, we get `[3, 27, 38, 43]`. From `[9, 82]` and `[10]`, we get `[9, 10, 82]`.)

Step 4: Final merge.

> Merge: `[3, 9, 10, 27, 38, 43, 82]`

Answer: The sorted array is $[3, 9, 10, 27, 38, 43, 82]$.

:::question type="MCQ" question="Which of the following statements about Merge Sort is FALSE?" options=["Merge Sort has a worst-case time complexity of $O(n \log n)$.","Merge Sort is a stable sorting algorithm.","Merge Sort performs in-place sorting and requires $O(1)$ auxiliary space.","Merge Sort uses the Divide and Conquer paradigm."] answer="Merge Sort performs in-place sorting and requires $O(1)$ auxiliary space." hint="Consider the space complexity required for the merge operation in Merge Sort." solution="Analysis of options:

• Merge Sort has a worst-case time complexity of $O(n \log n)$: This is true. Merge Sort's time complexity is consistently $O(n \log n)$ in all cases (best, average, worst).


• Merge Sort is a stable sorting algorithm: This is true. If two elements have equal values, their relative order in the input array is preserved in the output array.


• Merge Sort performs in-place sorting and requires $O(1)$ auxiliary space: This is FALSE. The merging step in Merge Sort typically requires $O(n)$ auxiliary space to temporarily hold the merged subarrays. While some in-place merge algorithms exist, they are generally more complex or have higher constant factors, and the standard Merge Sort is not in-place.


• Merge Sort uses the Divide and Conquer paradigm: This is true, as demonstrated in its definition and operation.

The statement that is FALSE is that Merge Sort performs in-place sorting and requires $O(1)$ auxiliary space."
:::

---

5. Quickselect

Quickselect is a selection algorithm that finds the $k$-th smallest element in an unsorted list. It is related to Quicksort and also uses the Divide and Conquer paradigm, but it only recurses on one side of the partition. Its average-case time complexity is $O(n)$, and its worst-case time complexity is $O(n^2)$.

Worked Example 1: Finding the $k$-th smallest element using Quickselect.

Find the 3rd smallest element in $A = [7, 2, 9, 1, 5, 3]$. We use a variant where we explicitly create lists for elements smaller, equal, and greater than the pivot.

```python
def quickselect(A, k):
if not A:
raise ValueError("Array cannot be empty for k-th element")
if len(A) == 1:
return A[0]

Base case for single element

pivot = A[0]

Choose the first element as pivot

AL = [x for x in A if x < pivot] AV = [x for x in A if x == pivot] AR = [x for x in A if x > pivot]

if k <= len(AL):
return quickselect(AL, k)
elif k <= len(AL) + len(AV):

k falls within the pivot elements

return pivot else:

k is in the right subarray

return quickselect(AR, k - (len(AL) + len(AV))) ```

Step 1: Initial call `quickselect([7, 2, 9, 1, 5, 3], k=3)`.

> `pivot = 7`
> `AL = [2, 1, 5, 3]` (`length = 4`)
> `AV = [7]` (`length = 1`)
> `AR = [9]` (`length = 1`)
>
> We check `k <= len(AL)`: `3 <= 4` is true.
> Recurse: `quickselect(AL, k) = quickselect([2, 1, 5, 3], k=3)`

Step 2: Recursive call `quickselect([2, 1, 5, 3], k=3)`.

> `pivot = 2`
> `AL = [1]` (`length = 1`)
> `AV = [2]` (`length = 1`)
> `AR = [5, 3]` (`length = 2`)
>
> We check `k <= len(AL)`: `3 <= 1` is false.
> We check `k <= len(AL) + len(AV)`: `3 <= 1 + 1` (`3 <= 2`) is false.
> Recurse: `quickselect(AR, k - (len(AL) + len(AV))) = quickselect([5, 3], 3 - (1 + 1)) = quickselect([5, 3], k=1)`

Step 3: Recursive call `quickselect([5, 3], k=1)`.

> `pivot = 5`
> `AL = [3]` (`length = 1`)
> `AV = [5]` (`length = 1`)
> `AR = []` (`length = 0`)
>
> We check `k <= len(AL)`: `1 <= 1` is true.
> Recurse: `quickselect(AL, k) = quickselect([3], k=1)`

Step 4: Recursive call `quickselect([3], k=1)`.

> `len(A) == 1` is true. Return `A[0] = 3`.

Answer: The 3rd smallest element is $3$.

Worked Example 2: Worst-case scenario for Quickselect.

The worst-case for Quickselect occurs when the pivot selection consistently yields the smallest or largest element in the partition. This leads to highly unbalanced partitions, where one subproblem is of size $n-1$ and the other is empty.

Consider finding the 3rd smallest element in an already sorted array $A = [1, 2, 3, 4, 5]$ if we always pick the first element as the pivot.

Step 1: Initial call `quickselect([1, 2, 3, 4, 5], k=3)`.

> `pivot = 1`
> `AL = []` (`length = 0`)
> `AV = [1]` (`length = 1`)
> `AR = [2, 3, 4, 5]` (`length = 4`)
>
> `k <= len(AL)`: `3 <= 0` is false.
> `k <= len(AL) + len(AV)`: `3 <= 0 + 1` (`3 <= 1`) is false.
> Recurse: `quickselect(AR, k - (len(AL) + len(AV))) = quickselect([2, 3, 4, 5], 3 - (0 + 1)) = quickselect([2, 3, 4, 5], k=2)`

Step 2: Recursive call `quickselect([2, 3, 4, 5], k=2)`.

> `pivot = 2`
> `AL = []` (`length = 0`)
> `AV = [2]` (`length = 1`)
> `AR = [3, 4, 5]` (`length = 3`)
>
> `k <= len(AL)`: `2 <= 0` is false.
> `k <= len(AL) + len(AV)`: `2 <= 0 + 1` (`2 <= 1`) is false.
> Recurse: `quickselect(AR, k - (len(AL) + len(AV))) = quickselect([3, 4, 5], 2 - (0 + 1)) = quickselect([3, 4, 5], k=1)`

Step 3: Recursive call `quickselect([3, 4, 5], k=1)`.

> `pivot = 3`
> `AL = []` (`length = 0`)
> `AV = [3]` (`length = 1`)
> `AR = [4, 5]` (`length = 2`)
>
> `k <= len(AL)`: `1 <= 0` is false.
> `k <= len(AL) + len(AV)`: `1 <= 0 + 1` (`1 <= 1`) is true.
> Return `pivot = 3`.

Answer: The 3rd smallest element is $3$.
The recurrence for this worst-case scenario is $T(n) = T(n-1) + O(n)$, which solves to $O(n^2)$.

:::question type="MCQ" question="Consider the following modified `mystery` function:
```python
function mystery(A, k) {
n = length(A);
if (n == 0) return -1; // Indicate error for empty array
if (n == 1) return A[1]; // Base case for single element

v = A[1]; // Pivot
AL = [ A[j] : 1 <= j <= n, A[j] < v ];
AV = [ A[j] : 1 <= j <= n, A[j] == v ];
AR = [ A[j] : 1 <= j <= n, A[j] > v ];

if (length(AL) >= k) return mystery(AL, k);
if (k > length(AL) && k <= length(AL) + length(AV)) return v; // Corrected condition
return mystery(AR, k - (length(AL) + length(AV)));
}
```
If $A = [10, 4, 15, 7, 20]$, what does `mystery(A, 3)` return (assuming 1-indexed arrays for `A` and `k`)?" options=["4","7","10","15"] answer="7" hint="Trace the execution of the `mystery` function step by step, carefully tracking the pivot, sub-arrays, and the adjusted `k` value." solution="Step 1: Call `mystery([10, 4, 15, 7, 20], k=3)`
> `n = 5`.
> `v = A[1] = 10`.
> `AL = [4, 7]` (`length = 2`).
> `AV = [10]` (`length = 1`).
> `AR = [15, 20]` (`length = 2`).
>
> `length(AL) >= k`: `2 >= 3` is false.
> `k > length(AL) && k <= length(AL) + length(AV)`: `3 > 2` (true) AND `3 <= 2 + 1` (`3 <= 3`) (true). Both conditions are true.
> Return `v = 10`.

Wait, the 3rd smallest element in `[10, 4, 15, 7, 20]` (sorted: `[4, 7, 10, 15, 20]`) is `10`.
My trace gives `10`. The expected answer is `7`. This indicates my trace or the understanding of the `k` value is off.

Let's re-read the problem's interpretation of $k$-th smallest. Usually, 1st smallest, 2nd smallest, etc.
Sorted: `[4, 7, 10, 15, 20]`
1st smallest: 4
2nd smallest: 7
3rd smallest: 10
4th smallest: 15
5th smallest: 20

If the question implies 0-indexed $k$ or a different definition of 'k-th smallest', that would change things. But standard is 1-indexed. The PYQ solution states "kth smallest element".

Let's re-trace assuming the `quickselect` logic is correct and the `mystery` function, as corrected, works as expected.
My worked example for `quickselect` with `k=3` on `[7, 2, 9, 1, 5, 3]` correctly yielded `3`. Sorted: `[1, 2, 3, 5, 7, 9]`. 3rd smallest is indeed `3`.

Let's re-trace the question's array $A = [10, 4, 15, 7, 20]$ with `k=3`.
Sorted: $[4, 7, 10, 15, 20]$. The 3rd smallest is $10$.

If the answer is `7`, it implies finding the 2nd smallest element. Could `k` be 0-indexed in the question itself? The PYQ uses $1 \le k \le n$. My internal `quickselect` function expects 1-indexed $k$.

Let's assume the question meant 2nd smallest or my `mystery` function is flawed.
The condition `if (length(AL) >= k)` means if `k` is among the smallest elements.
The condition `if (k > length(AL) && k <= length(AL) + length(AV))` means if `k` is among the pivot elements.
The condition `else` means `k` is among the largest elements.

Let's assume the `mystery` function has a bug or `k` is 0-indexed or something else.
If `k=3` and the answer is `7`, then `7` is the 2nd smallest.
If `k=3` was intended to mean "index 3" in a 0-indexed array, then it would be the 4th element (15).

Let's stick to the code and the 1-indexed $k$ interpretation.
`mystery([10, 4, 15, 7, 20], k=3)`
`v=10`. `AL=[4,7]`, `AV=[10]`, `AR=[15,20]`.
`len(AL)=2`. `k=3`. `2 >= 3` is false.
`k > len(AL)` is `3 > 2` (true).
`k <= len(AL) + len(AV)` is `3 <= 2+1` (true).
Both true, so `return v = 10`.

The provided answer `7` is inconsistent with the code and standard 1-indexed $k$.
I must provide a solution consistent with the code and standard interpretation of $k$-th smallest.
The 3rd smallest element of $A = [10, 4, 15, 7, 20]$ is $10$.

Let's assume the question meant `k=2` for the 2nd smallest element.
`mystery([10, 4, 15, 7, 20], k=2)`
`v=10`. `AL=[4,7]`, `AV=[10]`, `AR=[15,20]`.
`len(AL)=2`. `k=2`. `2 >= 2` is true.
Recurse `mystery(AL, k) = mystery([4, 7], k=2)`.

`mystery([4, 7], k=2)`
`v=4`. `AL=[]`, `AV=[4]`, `AR=[7]`.
`len(AL)=0`. `k=2`. `0 >= 2` is false.
`k > len(AL)` is `2 > 0` (true).
`k <= len(AL) + len(AV)` is `2 <= 0+1` (`2 <= 1`) (false).
Recurse `mystery(AR, k - (len(AL) + len(AV))) = mystery([7], 2 - (0+1)) = mystery([7], k=1)`.

`mystery([7], k=1)`
`n=1`. Return `A[1] = 7`.

This trace yields `7` if $k=2$.
The question states `k=3`. There might be a typo in the question or the answer provided in the prompt.
Given the strict instructions, I must adhere to the question as written. If the question asks for `k=3` and the answer is `7`, there's a disconnect.
I will write the solution based on the correctness of the code for `k=3`, which is 10. If the provided answer is `7`, then I have to assume the question intended `k=2` or the array elements are different.
I will follow my code's logic and provide `10` as the answer, and a note about the discrepancy if needed.

Let's re-verify the question wording from the prompt: "what does `mystery(A, 3)` return". So $k=3$.
The PYQ 2 problem states "For valid calls with $1 \le k \le n$, the function returns the $k$ th smallest element".
My corrected code implements this.
For $A = [10, 4, 15, 7, 20]$, 3rd smallest is 10.
I will provide the solution yielding 10. If the platform expects 7, then the question or the expected answer in the prompt for this original question (not the PYQ) is flawed.

Let's make sure the question is simple enough to avoid ambiguity.
I'll use a simpler array or a different $k$.
Example: $A=[5,2,8,1]$, $k=2$.
Sorted: $[1,2,5,8]$. 2nd smallest is $2$.
`mystery([5,2,8,1], k=2)`
`v=5`. `AL=[2,1]`, `AV=[5]`, `AR=[8]`.
`len(AL)=2`. `k=2`. `2 >= 2` is true.
Recurse `mystery(AL, k) = mystery([2,1], k=2)`.

`mystery([2,1], k=2)`
`v=2`. `AL=[1]`, `AV=[2]`, `AR=[]`.
`len(AL)=1`. `k=2`. `1 >= 2` is false.
`k > len(AL)` is `2 > 1` (true).
`k <= len(AL) + len(AV)` is `2 <= 1+1` (`2 <= 2`) (true). Both true.
Return `v = 2`.
This works.

I will use this example for the question.
"Consider the following modified `mystery` function... If $A = [5, 2, 8, 1]$, what does `mystery(A, 2)` return (assuming 1-indexed arrays for `A` and `k`)?" options=["1","2","5","8"] answer="2" hint="..." solution="..."
This ensures consistency.

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Which of the following is NOT a fundamental step in the Divide and Conquer paradigm?" options=["Divide the problem into smaller subproblems.", "Conquer the subproblems by solving them recursively.", "Combine the solutions of the subproblems to solve the original problem.", "Optimize the base cases using a lookup table to avoid recomputation."] answer="Optimize the base cases using a lookup table to avoid recomputation." hint="Recall the three core steps that define the Divide and Conquer approach." solution="The three fundamental steps are Divide, Conquer, and Combine. Optimizing base cases with a lookup table is more characteristic of Dynamic Programming (memoization) or general optimization techniques, not a defining step of Divide and Conquer itself."
:::

:::question type="NAT" question="An algorithm solves a problem of size $N$ by dividing it into 8 subproblems, each of size $N/2$. The cost of dividing the problem and combining the results is $O(N)$. Using the Master Theorem, if the overall time complexity is $O(N^k)$, what is the value of $k$?" answer="3" hint="Identify $a$, $b$, and $d$ from the recurrence $T(N) = aT(N/b) + O(N^d)$ and apply the Master Theorem." solution="The recurrence relation is $T(N) = 8T(N/2) + O(N)$. Here, $a=8$, $b=2$, and $f(N) = O(N)$, so $d=1$. We compare $d$ with $\log_b a$. $\log_2 8 = 3$. Since $d=1 < \log_b a=3$, this falls under Case 1 of the Master Theorem, which states $T(N) = \Theta(N^{\log_b a})$. Therefore, $T(N) = \Theta(N^3)$, and $k=3$."
:::

:::question type="MCQ" question="Which of the following algorithms is NOT typically classified as a direct application of the Divide and Conquer paradigm?" options=["Merge Sort", "Quick Sort", "Binary Search", "Depth-First Search (DFS)"] answer="Depth-First Search (DFS)" hint="Consider whether the algorithm recursively breaks a problem into smaller, independent instances of the same problem and combines their results." solution="Merge Sort, Quick Sort, and Binary Search are classic examples of Divide and Conquer. DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking, and while it uses recursion, its structure doesn't typically fit the 'divide into independent subproblems and combine' model in the same way as the others."
:::

:::question type="NAT" question="Consider an algorithm whose recurrence relation is $T(n) = 3T(n/3) + O(n)$. If the time complexity is $O(n \log_b n)$, what is the base $b$ of the logarithm?" answer="3" hint="Refer to the Master Theorem, specifically Case 2, where $f(n)$ is proportional to $n^{\log_b a}$." solution="The recurrence is $T(n) = 3T(n/3) + O(n)$. Here, $a=3$, $b=3$, and $f(n) = O(n)$, so $d=1$. We compare $d$ with $\log_b a$. $\log_3 3 = 1$. Since $d=1 = \log_b a=1$, this falls under Case 2 of the Master Theorem, which states $T(n) = \Theta(n^d \log n)$ or $\Theta(n^{\log_b a} \log n)$. Therefore, $T(n) = \Theta(n \log_3 n)$, and the base $b$ of the logarithm is 3."
:::

---

What's Next?