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

Recall & Review

beginner

What is the Divide and Conquer strategy in algorithms?

Divide and Conquer is a method where a problem is split into smaller subproblems, each solved independently, and then combined to get the final solution.

beginner

Explain what a recurrence relation is in the context of Divide and Conquer.

A recurrence relation expresses the total time of an algorithm in terms of the time taken by smaller subproblems plus the time to combine their results.

intermediate

Example: What is the recurrence relation for Merge Sort?

T(n) = 2 * T(n/2) + O(n), where 2 * T(n/2) is the time for sorting two halves and O(n) is the time to merge them.

intermediate

What does the Master Theorem help with?

The Master Theorem provides a quick way to solve recurrence relations of Divide and Conquer algorithms to find their time complexity.

beginner

Why is Divide and Conquer efficient for large problems?

Because it breaks a big problem into smaller parts, solves them independently, often in parallel, and combines results efficiently, reducing overall work.

What is the first step in the Divide and Conquer approach?

A Ignore the problem

B Combine the results

C Solve the problem directly

D Divide the problem into smaller subproblems

The first step is to divide the problem into smaller subproblems.

Which recurrence relation matches the Quick Sort average case?

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

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

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

D T(n) = T(n/2) + O(1)

Quick Sort average case recurrence is approximately T(n) = T(n-1) + O(n). The recurrence T(n) = 2 * T(n/2) + O(n) assumes perfectly balanced partitions, which is not typical for Quick Sort.

What does the term 'conquer' mean in Divide and Conquer?

A Splitting the problem

B Solving the subproblems

C Combining the results

D Ignoring subproblems

'Conquer' means solving the smaller subproblems after dividing.

Which of these is NOT a step in Divide and Conquer?

A Iterate

B Conquer

C Divide

D Combine

'Iterate' is not a standard step in Divide and Conquer.

What does the Master Theorem require to solve a recurrence?

A Number of subproblems, size of each subproblem, and cost to combine

B Only the size of the problem

C Only the number of subproblems

D Only the cost to combine

Master Theorem uses number of subproblems, their size, and combine cost.

Describe the three main steps of the Divide and Conquer strategy with an example.

Think about how a big problem is split, solved, and results joined.

Explain how recurrence relations help analyze the time complexity of Divide and Conquer algorithms.

Focus on expressing time in terms of smaller parts.