試題詳解

13. Consider a divide-and-conquer algorithm, which solves a problem of size n by dividing it into two subproblems of size n/3 and n/5, respectively. The solutions of the subproblems are then combined in θ(n²) time. Which of the following is correct about the time complexity T(n) of this algorithm?
(A) T(n) must be in θ(n²).
(B) T(n) must be in O(n²) but not nec ssarily in Ω(n²).
(C) T(n) must be in Ω(n²) but not necessarily in O(n²).
(D)None of the above. The complexity of T(n) depends on the exact valuc of n.