Divide Conquer Quiz — A-Level Computer Science

Question 1

When analyzing the time complexity of a Divide and Conquer algorithm, which of the following best describes the purpose of the Master Theorem?

Question 2

Consider a Divide and Conquer algorithm for finding the maximum element in an array. The array is recursively split into two halves until a single element is reached. The 'Combine' step involves comparing the maximums of the two halves. Which of the following recurrence relations correctly represents the time complexity of this algorithm, and what is its asymptotic solution?

Question 3

A Divide and Conquer algorithm for finding the closest pair of points in a 2D plane works by dividing the set of $N$ points into two halves, recursively finding the closest pair in each half, and then considering pairs where one point is in each half (the 'split pair' step). If the split pair step, which involves sorting a subset of points and iterating through them, takes $O(N)$ time, what is the recurrence relation for the time complexity, and what is its asymptotic solution?

Question 4

When analyzing the space complexity of a recursive Divide and Conquer algorithm, what is the primary factor that often contributes to the auxiliary space used, beyond the input storage itself?

Question 5

A Divide and Conquer algorithm is used to count the number of inversions in an array. An inversion is a pair of indices $(i, j)$ such that $i < j$ and $A[i] > A[j]$. The algorithm works by dividing the array into two halves, recursively counting inversions in each half, and then counting 'split inversions' (where one element is in the left half and the other in the right) during a modified merge step. If the merge step takes $O(N)$ time to count split inversions and combine the sorted halves, what is the recurrence relation for the time complexity, and what is its asymptotic solution?

Divide Conquer — Quiz

Practice Questions