Solution

The correct answer is (A), (E), (D), (B), (C)

Key Points

• (A) T(n) = T(n/2) + 1: This is a logarithmic recurrence relation, which solves to T(n) = O(log n).
• (E) T(n) = T(n - 1) + 1: This is a linear recurrence relation, which solves to T(n) = O(n).
• (D) T(n) = 2T(n/2) + √n: This can also be solved using the Master Theorem. The solution is O(n), as the extra cost outside the recursion is O(√n).
• (B) T(n) = 2T(n/2) + n: This is a recurrence relation that can be solved using the Master Theorem. It falls into case 2 (a = b^c), which gives T(n) = O(n log n).
• (C) T(n) = 3T(n/3) + n: This is another recurrence relation that can be solved using the Master Theorem. It falls into case 2 (a = b^c), which gives T(n) = O(n log n). 

Thus the correct answer is ​(A), (E), (D), (B), (C)

Additional Information

• The recurrence relation T(n) = T(n-1) + 1 is the simplest and grows linearly with n.
• The recurrence relation T(n) = T(n/2) + 1 grows logarithmically, which is faster than linear growth but slower than polynomial or exponential growth.
• Using the Master Theorem helps in solving more complex recurrence relations like T(n) = 2T(n/2) + n, T(n) = 2T(n/2) + √n, and T(n) = 3T(n/3) + n, all of which grow faster than the linear and logarithmic cases but at different rates.
• Understanding the growth rates of these recurrence relations is crucial for analyzing the time complexity of algorithms, especially in competitive exams and technical interviews.