The generic divide-and-conquer recurrence, with `a` sub-problems of size `n/b` and divide+combine work `g(n)`, is
A$T(n) = a \cdot T(n/b) + g(n)$
B$T(n) = T(n-1) + a \cdot g(n)$
C$T(n) = a^n + b \cdot g(n)$
D$T(n) = a + b \cdot T(n) + g(n)$
Answer & Solution
Correct answer: A. $T(n) = a \cdot T(n/b) + g(n)$
The textbook D&C template: each level does g(n) divide-and-combine work, then recurses on `a` sub-problems of size n/b. Master Theorem reads off solutions directly from this shape. The other options describe linear recurrences (T(n-1)+g(n) is insertion sort), exponential growth, or are not well-formed.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for