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.