Divide and Conquer Strategy and Recurrence Relations in DSA Rust - Execution Trace

Concept Flow - Divide and Conquer Strategy and Recurrence Relations

Divide Problem

↓

Divide into Subproblems

↓

Recursively Solve Subproblems

↓

Combine Subproblem Solutions

↓

Final Solution

The problem is split into smaller parts, each solved recursively, then combined to form the final answer.

Execution Sample

DSA Rust

fn divide_and_conquer(n: usize) -> usize {
    if n == 1 {
        return 1;
    }
    let half = n / 2;
    divide_and_conquer(half) + divide_and_conquer(half)
}

This function divides the input size by half recursively until base case, then combines results by addition.

Execution Table

Step	Operation	Input Size (n)	Recursive Calls	Return Value	Recurrence Relation Visual
1	Call divide_and_conquer(8)	8	Calls divide_and_conquer(4) twice	-	T(8) = 2 * T(4) + O(1)
2	Call divide_and_conquer(4)	4	Calls divide_and_conquer(2) twice	-	T(4) = 2 * T(2) + O(1)
3	Call divide_and_conquer(2)	2	Calls divide_and_conquer(1) twice	-	T(2) = 2 * T(1) + O(1)
4	Call divide_and_conquer(1)	1	Base case reached	1	T(1) = O(1)
5	Return from divide_and_conquer(1)	1	No calls	1	-
6	Return from divide_and_conquer(2)	2	Completed calls	1 + 1 = 2	-
7	Return from divide_and_conquer(4)	4	Completed calls	2 + 2 = 4	-
8	Return from divide_and_conquer(8)	8	Completed calls	4 + 4 = 8	-
9	End	-	-	-	Recursion ends as base cases reached and combined

💡 Recursion stops when input size reaches 1 (base case), then results combine upwards.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 6	After Step 7	Final
n	8	8	4	2	1	2	4	8
Return Value	-	-	-	-	1	2	4	8
Recursive Calls	0	2 calls with n=4	2 calls with n=2	2 calls with n=1	Base case	Completed calls	Completed calls	Completed calls

Key Moments - 3 Insights

Why does the recursion stop at n == 1?

Because n == 1 is the base case where the problem is simple enough to solve directly, as shown in execution_table row 4.

How do the recursive calls combine their results?

Each call returns a value that is added together in the parent call, as seen in rows 6, 7, and 8 where results from smaller calls sum up.

What does the recurrence relation T(n) = 2*T(n/2) + O(1) mean?

It means the problem of size n is divided into two subproblems of size n/2, solved recursively, plus a constant amount of work to combine results, as shown in the 'Recurrence Relation Visual' column.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value of divide_and_conquer(2) at step 6?

A 1

B 2

C 4

D 8

💡 Hint

Check the 'Return Value' column at step 6 in the execution_table.

At which step does the recursion reach the base case?

A Step 4

B Step 3

C Step 6

D Step 8

💡 Hint

Look for 'Base case reached' in the 'Operation' column of the execution_table.

If the function called divide_and_conquer(16) instead of 8, how many recursive calls to divide_and_conquer(1) would occur?

A 8

B 32

C 16

D 64

💡 Hint

Recall that each call splits into two calls until n=1; doubling input doubles calls exponentially.

Concept Snapshot

Divide and Conquer splits a problem into smaller parts,
solves each recursively, then combines results.
Recurrence relations express time as T(n) = a*T(n/b) + f(n).
Base case stops recursion (e.g., n=1).
Example: T(n) = 2*T(n/2) + O(1) means two halves plus constant work.
Used in sorting, searching, and many algorithms.

Full Transcript

Divide and Conquer is a method where a big problem is broken into smaller problems. Each smaller problem is solved by calling the same method again, but with a smaller input. This continues until the problem is simple enough to solve directly, called the base case. After solving the small problems, their answers are combined to get the final solution. The time taken by such algorithms can be described by recurrence relations, which show how the time depends on the size of the input and the time for smaller inputs. For example, if a problem of size n is split into two problems of size n/2, and some constant work is done to combine results, the relation is T(n) = 2*T(n/2) + O(1). This helps us understand and analyze the efficiency of divide and conquer algorithms.

Practice

1. What is the main idea behind the Divide and Conquer strategy in algorithms?

easy

A. Break the problem into smaller subproblems, solve them independently, then combine results

B. Solve the problem by trying all possible solutions one by one

C. Use a single loop to iterate through all elements

D. Store all intermediate results to avoid repeated calculations

Solution

1. Step 1: Understand the divide and conquer approach

   It splits a big problem into smaller parts that are easier to solve.

2. Step 2: Combine the solutions of subproblems

   After solving smaller parts, their results are merged to get the final answer.

3. Final Answer:

   Break the problem into smaller subproblems, solve them independently, then combine results -> Option A

4. Quick Check:

   Divide and conquer = split, solve, combine [OK]

Hint: Divide big problem into smaller parts, solve, then merge [OK]

Common Mistakes:

• Confusing divide and conquer with brute force
• Thinking it uses only one loop
• Mixing with dynamic programming concepts

2. Which of the following is the correct Rust syntax to define a recursive function for the divide and conquer approach?

easy

A. fn divide_and_conquer(n: i32) -> i32 { if n == 0 { 0 } else { n * divide_and_conquer(n) } }

B. fn divide_and_conquer(n: i32) { while n > 1 { n -= 1; } }

C. fn divide_and_conquer(n: i32) -> i32 { loop { return n; } }

D. fn divide_and_conquer(n: i32) -> i32 { if n == 1 { 1 } else { divide_and_conquer(n - 1) + 1 } }

Solution

1. Step 1: Check for base case in recursion

   fn divide_and_conquer(n: i32) -> i32 { if n == 1 { 1 } else { divide_and_conquer(n - 1) + 1 } } has a base case: if n == 1 returns 1, which stops recursion.

2. Step 2: Verify recursive call reduces problem size

   fn divide_and_conquer(n: i32) -> i32 { if n == 1 { 1 } else { divide_and_conquer(n - 1) + 1 } } calls divide_and_conquer(n - 1), reducing n each time.

3. Final Answer:

   fn divide_and_conquer(n: i32) -> i32 { if n == 1 { 1 } else { divide_and_conquer(n - 1) + 1 } } -> Option D

4. Quick Check:

   Recursive function needs base case and smaller input [OK]

Hint: Look for base case and smaller recursive call [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Not reducing input in recursive call
• Using loops instead of recursion

3. Consider the following Rust function implementing merge sort. What will be the output when calling merge_sort(vec![3, 1, 4, 2])?

fn merge_sort(mut arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }
    let mid = arr.len() / 2;
    let left = merge_sort(arr.drain(..mid).collect());
    let right = merge_sort(arr);
    merge(left, right)
}

fn merge(left: Vec<i32>, right: Vec<i32>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut i = 0;
    let mut j = 0;
    while i < left.len() && j < right.len() {
        if left[i] < right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }
    result.extend_from_slice(&left[i..]);
    result.extend_from_slice(&right[j..]);
    result
}

medium

A. [3, 1, 4, 2]

B. [4, 3, 2, 1]

C. [1, 2, 3, 4]

D. [1, 3, 2, 4]

Solution

1. Step 1: Understand merge sort splits and sorts

   The function splits the array into halves recursively until size 1, then merges sorted halves.

2. Step 2: Trace sorting of input [3, 1, 4, 2]

   Splitting: [3,1] and [4,2], then [3], [1], [4], [2]. Merging sorted pairs: [1,3] and [2,4]. Final merge: [1,2,3,4].

3. Final Answer:

   [1, 2, 3, 4] -> Option C

4. Quick Check:

   Merge sort output is sorted array ascending [OK]

Hint: Merge sort always returns sorted array ascending [OK]

Common Mistakes:

• Confusing merge order causing reversed output
• Not understanding recursive splitting
• Ignoring that merge combines sorted halves

4. The following Rust function is intended to compute the Fibonacci number using divide and conquer. Identify the bug:

fn fib(n: u32) -> u32 {
    if n <= 1 {
        return n;
    }
    fib(n - 1) + fib(n - 1)
}

medium

A. It misses the base case for n == 0

B. It calls fib(n - 1) twice instead of fib(n - 1) and fib(n - 2)

C. It uses u32 instead of i32 for n

D. It should use a loop instead of recursion

Solution

1. Step 1: Check recursive calls in function

   The function calls fib(n - 1) twice, which is incorrect for Fibonacci.

2. Step 2: Recall Fibonacci formula

   Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2), so one call should be fib(n - 2).

3. Final Answer:

   It calls fib(n - 1) twice instead of fib(n - 1) and fib(n - 2) -> Option B

4. Quick Check:

   Fibonacci needs fib(n-1) + fib(n-2) [OK]

Hint: Fibonacci sums fib(n-1) and fib(n-2) [OK]

Common Mistakes:

• Calling fib(n-1) twice causing wrong results
• Ignoring base cases
• Confusing parameter types

5. Given the recurrence relation T(n) = 2T(n/2) + n, which of the following is the correct time complexity using the Master Theorem?

hard

A. O(n log n)

B. O(n^2)

C. O(log n)

D. O(n)

Solution

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

   Here, a = 2, b = 2, and f(n) = n.

2. Step 2: Calculate log_b(a)

   log_2(2) = 1.

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

   f(n) = n and n^{log_b(a)} = n^1 = n, so f(n) = Theta(n^{log_b(a)}).

4. Step 4: Apply Master Theorem case 2

   When f(n) = Theta(n^{log_b(a)}), T(n) = Theta(n log n).

5. Final Answer:

   O(n log n) -> Option A

6. Quick Check:

   Master theorem case 2 gives O(n log n) [OK]

Hint: Use Master Theorem: compare f(n) to n^{log_b(a)} [OK]

Common Mistakes:

• Confusing log base or parameters a and b
• Choosing wrong Master Theorem case
• Ignoring the additive term f(n)