Solution

The correct answer is A - I, B - III, C - IV, D - II

Key Points

• T(n) = 2T(n/2) + n:
  • This recurrence relation can be solved using the Master Theorem. Here, a = 2, b = 2, and f(n) = n. According to the Master Theorem, if f(n) = Θ(n^c) where c = log_b(a), then T(n) = Θ(n^c log^k n). Since c = log_2(2) = 1, T(n) = Θ(n log n). So, A matches with I.
• T(n) = T(n/2) + 1:
  • This recurrence relation can be solved by the method of iteration. By expanding the terms, we get T(n) = T(n/2) + 1 = T(n/4) + 2 = ... = T(1) + log_2(n). Therefore, T(n) = Θ(log n). So, B matches with III.
• T(n) = 2T(n/2) + 1:
  • Using the Master Theorem, where a = 2, b = 2, and f(n) = 1. Here, f(n) = O(n^c) where c = log_b(a) = log_2(2) = 1. Since f(n) is O(n^c) and not Θ(n^c), T(n) = O(n). So, C matches with IV.
• T(n) = T(n - 1) + 1:
  • This recurrence relation can be solved using the iteration method. By expanding the terms, we get T(n) = T(n-1) + 1 = T(n-2) + 2 = ... = T(1) + (n-1). Therefore, T(n) = Θ(n). So, D matches with II.

Therefore, the correct option is A - I, B - III, C - IV, D - II. So, the correct option is 3).