Karatsuba's recurrence for n-digit multiplication is
AT(n) = T(n/2) + Θ(n)
BT(n) = 4T(n/2) + Θ(n)
CT(n) = 2T(n/2) + Θ(n)
DT(n) = 3T(n/2) + Θ(n)
Answer & Solution
Correct answer: D. T(n) = 3T(n/2) + Θ(n)
Karatsuba reduces the product of two n-digit numbers to THREE products of (n/2)-digit numbers plus linear additions. Hence T(n) = 3T(n/2) + Θ(n), which by master theorem gives O(n^log_2 3) ≈ O(n^1.58). Four sub-problems would be the naive split (giving O(n²) again); two would beat the actual O(n log n) for sorting, which Karatsuba does not do.
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