Divide and Conquer Strategy and Recurrence Relations in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Divide and Conquer strategy?

Divide and Conquer is a method where a problem is split into smaller parts, each part is solved separately, and then the solutions are combined to solve the original problem.

beginner

Explain what a recurrence relation is in the context of algorithms.

A recurrence relation is an equation that defines a sequence where each term is based on previous terms. In algorithms, it expresses the running time of a recursive function in terms of smaller inputs.

intermediate

Give an example of a common recurrence relation for a divide and conquer algorithm.

T(n) = 2T(n/2) + O(n) is a common recurrence relation where the problem is divided into two halves, solved recursively, and combined in linear time.

intermediate

What is the Master Theorem used for?

The Master Theorem helps solve recurrence relations of divide and conquer algorithms to find their time complexity quickly without expanding the recurrence.

beginner

Why is the divide and conquer strategy efficient for sorting algorithms like Merge Sort?

Because it breaks the list into smaller parts, sorts each part quickly, and merges them efficiently, reducing the overall time compared to sorting the whole list at once.

What are the three main steps in the divide and conquer approach?

A Divide, Conquer, Combine

B Divide, Solve, Combine

C Split, Solve, Merge

D Divide, Solve, Merge

The three steps are Divide the problem, Conquer by solving subproblems, and Combine the results.

Which recurrence relation corresponds to an algorithm that splits the problem into four parts, each of size n/4?

A T(n) = 2T(n/2) + O(n)

B T(n) = 4T(n/4) + O(n)

C T(n) = T(n-1) + O(1)

D T(n) = 3T(n/3) + O(n^2)

Splitting into four parts with each subproblem size n/4 leads to T(n) = 4T(n/4) plus the combining cost.

What does the term 'recurrence relation' describe in algorithm analysis?

A The base case of recursion

B The time complexity formula for iterative algorithms

C The space used by an algorithm

D The running time expressed in terms of smaller inputs

Recurrence relations express running time based on smaller input sizes in recursive algorithms.

Which of these is NOT a step in solving a recurrence relation using the Master Theorem?

A Identify a, b, and f(n) in T(n) = aT(n/b) + f(n)

B Compare f(n) with n^log_b(a)

C Expand the recurrence fully by substitution

D Apply the correct case of the theorem

The Master Theorem avoids full expansion by using a formula and comparisons.

What is the time complexity of Merge Sort using divide and conquer?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

Merge Sort divides the list and merges in linear time, resulting in O(n log n) complexity.

Describe the divide and conquer strategy and how it helps solve problems efficiently.

Think about how breaking a big task into smaller tasks can make it easier.

Explain what a recurrence relation is and how it is used to analyze recursive algorithms.

Consider how the time for a big problem depends on the time for smaller problems.

Practice

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

easy

A. Use a single loop to solve the problem iteratively

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

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

D. Store all intermediate results to avoid repeated calculations

Solution

1. Step 1: Understand Divide and Conquer approach

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

2. Step 2: Combine solutions of subproblems

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

3. Final Answer:

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

4. Quick Check:

   Divide and Conquer = Break, Solve, Combine [OK]

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

Common Mistakes:

• Confusing divide and conquer with brute force
• Thinking it uses only loops without recursion
• Mixing it up with dynamic programming

2. Which of the following is the correct recurrence relation for the Merge Sort algorithm on an array of size n?

easy

A. T(n) = T(n-1) + O(1)

B. T(n) = 2T(n/2) + O(n)

C. T(n) = T(n/2) + O(1)

D. T(n) = 3T(n/3) + O(n^2)

Solution

1. Step 1: Recall Merge Sort process

   Merge Sort splits array into two halves, sorts each half recursively, then merges in O(n) time.

2. Step 2: Write recurrence relation

   It calls itself twice on size n/2 plus linear merge step, so T(n) = 2T(n/2) + O(n).

3. Final Answer:

   T(n) = 2T(n/2) + O(n) -> Option B

4. Quick Check:

   Merge Sort recurrence = 2 halves + merge O(n) [OK]

Hint: Two halves plus linear merge step means 2T(n/2)+n [OK]

Common Mistakes:

• Using T(n-1) instead of T(n/2)
• Ignoring the merge step cost
• Confusing with quicksort recurrence

3. Consider the following C code implementing a divide and conquer function:

int func(int n) {
    if (n <= 1) return 1;
    return func(n/2) + func(n/2) + n;
}

What is the time complexity T(n) of this function?

medium

A. O(n^2)

B. O(n)

C. O(log n)

D. O(n log n)

Solution

1. Step 1: Identify recurrence relation

   The function calls itself twice on n/2 plus does O(n) work, so T(n) = 2T(n/2) + n.

2. Step 2: Solve recurrence using Master Theorem

   For T(n) = 2T(n/2) + n, the solution is O(n log n).

3. Final Answer:

   O(n log n) -> Option D

4. Quick Check:

   2 calls on half + linear work = n log n [OK]

Hint: Two halves plus linear work means n log n time [OK]

Common Mistakes:

• Thinking it is O(n) by ignoring recursive calls
• Confusing with O(log n) for single call
• Mistaking it for quadratic O(n^2)

4. The following recurrence relation is given:

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

There is a mistake in the code implementing this recurrence. Which fix will correct the recurrence to match the intended divide and conquer approach?

medium

A. Change the recursive calls to 3T(n/3) and keep n^2 as extra work

B. Change the extra work from n^2 to n log n

C. Change the recursive calls to T(n-1) and keep n^2

D. Change the recursive calls to 2T(n/2) and keep n^2

Solution

1. Step 1: Understand the recurrence meaning

   3T(n/3) means dividing problem into 3 equal parts recursively, plus n^2 extra work.

2. Step 2: Fix code to match recurrence

   Ensure code calls itself 3 times on n/3 size and does n^2 work outside recursion.

3. Final Answer:

   Change the recursive calls to 3T(n/3) and keep n^2 as extra work -> Option A

4. Quick Check:

   3 recursive calls on n/3 + n^2 work = 3T(n/3)+n^2 [OK]

Hint: Match recursive calls count and size to recurrence exactly [OK]

Common Mistakes:

• Changing extra work without fixing recursive calls
• Using wrong subproblem size like n-1
• Reducing calls to 2 instead of 3

5. You have a problem of size n that you divide into 4 subproblems each of size n/2. The extra work done outside the recursive calls is O(n^2). What is the time complexity T(n) of this divide and conquer algorithm?

hard

A. O(n^2 log n)

B. O(n^3)

C. O(n^2)

D. O(n log n)

Solution

1. Step 1: Write the recurrence relation

   Since there are 4 subproblems each size n/2 and extra work n^2, T(n) = 4T(n/2) + n^2.

2. Step 2: Apply Master Theorem

   Here, a=4, b=2, f(n)=n^2. Calculate log_b(a) = log_2(4) = 2. Since f(n) = Theta(n^2), it matches n^{log_b(a)}.

3. Step 3: Determine complexity

   By Master Theorem case 2, T(n) = Theta(n^2 log n).

4. Final Answer:

   O(n^2 log n) -> Option A

5. Quick Check:

   4 calls on half + n^2 work = n^2 log n [OK]

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

Common Mistakes:

• Ignoring the log factor in complexity
• Confusing number of subproblems with size
• Mistaking it for cubic or linear complexity