An algorithm splits a problem into 3 independent subproblems of size n/3 and combines their results in O(n) time. Applying the Master Theorem (a=3, b=3, f(n)=O(n)), what is the overall time complexity?
AO(n)
BO(n log n)
CO(n²)
DO(log n)
With a=3, b=3: n^(log_b a) = n^(log_3 3) = n^1 = n. Since f(n) = O(n) = Θ(n^(log_b a)), we're in Master Theorem case 2: T(n) = Θ(n log n). The divide/combine work matches the recursive branching at every level, producing a log factor. If f(n) were O(n²), the root would dominate and we'd get O(n²); if f(n) were O(log n), the leaves would dominate and we'd get O(n).
Question 2 Multiple Choice
What is the essential property that distinguishes divide and conquer from dynamic programming?
ADivide and conquer always achieves better time complexity than dynamic programming
BDivide and conquer is iterative while dynamic programming is recursive
CIn divide and conquer, the subproblems are independent; in dynamic programming, subproblems overlap and share results
DDivide and conquer can only be applied to sorting and searching problems
Independence is the defining criterion. Divide and conquer solves each subproblem fresh, with no shared work between them — merge sort's left and right halves are solved entirely separately. Dynamic programming is the right tool when subproblems recur and their results can be reused (memoized). Applying divide and conquer to overlapping subproblems results in exponential redundancy (the classic example: naive recursive Fibonacci). The choice between paradigms depends entirely on whether subproblems share structure.
Question 3 True / False
In a typical divide and conquer algorithm, the combine step is often where most of the computational work occurs.
TTrue
FFalse
Answer: True
True — merge sort is the canonical example. Splitting an array in half takes O(1) (just compute the midpoint). But merging two sorted halves takes O(n). The character of the algorithm is defined by its combine step. This is a common surprise for students who assume 'divide' is the hard part. The Master Theorem formalizes this: f(n), the divide/combine cost, often determines the overall complexity.
Question 4 True / False
Binary search is a straightforward example of divide and conquer because it recursively processes both halves of the sorted array.
TTrue
FFalse
Answer: False
False — binary search only recurses on one subproblem (the half that might contain the target). True divide and conquer recurses on all subproblems and combines their results. Binary search discards one half entirely and never combines anything. This pattern is sometimes called 'decrease and conquer.' The distinction matters for complexity: binary search does O(log n) work precisely because it processes one subproblem instead of two.
Question 5 Short Answer
In the Master Theorem recurrence T(n) = aT(n/b) + f(n), what do a, b, and f(n) represent, and what comparison drives the theorem's three cases?
Think about your answer, then reveal below.
Model answer: a = the number of subproblems the algorithm creates; b = the factor by which each subproblem's size is reduced; f(n) = the cost of the divide and combine steps (excluding the recursive calls). The theorem compares f(n) to n^(log_b a), which represents the total work done at the leaves of the recursion tree. If f grows slower than n^(log_b a), the leaf level dominates; if f grows faster, the top-level (root) work dominates; if they match, the work is spread evenly across all log n levels and a log factor appears.
The recursion tree picture makes this intuitive: each level multiplies the number of subproblems by a while shrinking each by 1/b. The total leaf-level work is n^(log_b a). Whether the combine work f(n) overwhelms this, matches it, or is swamped by it determines which term dominates the overall complexity.