If T(1) = O(1), match the following recurrence relations with their asymptotic…
1999
If T(1) = O(1), match the following recurrence relations with their asymptotic bounds: (M) T(n) = T(n - 1) + n; (N) T(n) = T(n/2) + n; (O) T(n) = T(n/2) + n log n; (P) T(n) = T(n - 1) + log n. Bounds: (U) T(n) = O(n); (V) T(n) = O(n log n); (W) T(n) = O(n^2); (X) T(n) = O(log^2 n).
- A.
M-W, N-V, O-U, P-X
- B.
M-W, N-U, O-X, P-V
- C.
M-V, N-W, O-X, P-U
- D.
M-W, N-U, O-V, P-V
Attempted by 6 students.
Show answer & explanation
Correct answer: D
Match each recurrence by expansion or the Master theorem. For M, T(n) = T(n - 1) + n gives 1 + 2 + ... + n, so T(n) = O(n^2), matching W. For N, T(n) = T(n/2) + n gives the series n + n/2 + n/4 + ..., so T(n) = O(n), matching U. For O, T(n) = T(n/2) + n log n gives costs n log n, (n/2)(log n - 1), (n/4)(log n - 2), ..., whose sum is O(n log n), matching V. For P, T(n) = T(n - 1) + log n gives log 1 + log 2 + ... + log n = log(n!) = O(n log n), matching V. Therefore, the mathematically correct matching is M-W, N-U, O-V, P-V. A printed option that maps P to X would be inconsistent with the recurrence T(n) = T(n - 1) + log n.