The recurrence relation for merge sort's running time is
AT(n) = T(n-1) + Θ(n)
BT(n) = 2T(n-1) + Θ(1)
CT(n) = T(n/2) + Θ(1)
DT(n) = 2T(n/2) + Θ(n)
Answer & Solution
Correct answer: D. T(n) = 2T(n/2) + Θ(n)
Merge sort makes two recursive calls on halves of the input (2T(n/2)) and then does a linear merge (Θ(n)). The master theorem solves this to Θ(n log n). The other options describe different algorithms: T(n-1)+Θ(n) is insertion sort's worst case, T(n/2)+Θ(1) is binary search, 2T(n-1)+Θ(1) is exponential.
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