Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is…

Solution:

Apply the Master theorem to the recurrence T(n) = 2T(n/2) + n.

Compute parameters: a = 2, b = 2, so n^{log_b a} = n^{log_2 2} = n. The nonrecursive term is f(n) = n.

• Compare f(n) with n^{log_b a}: f(n) = n = Θ(n^{log_b a}).

• This fits case 2 of the Master theorem, giving T(n) = Θ(n^{log_b a} · log n) = Θ(n log n).

Therefore T(n) = Θ(n log n).

Conclusion: The statement claiming T(n) = Ω(n 2 ) is false because Θ(n log n) grows strictly slower than n^2 (n log n = o(n^2)). The other statements are true: T(n) = Θ(n log n) (tight), so T(n) = O(n log n) and T(n) = O(n 2 ) hold.

• T(n) = O(n 2 ): True (loose bound) — Θ(n log n) = O(n^2).

• T(n) = θ(n log n): True (tight bound by Master theorem).

• T(n) = Ω(n 2 ): False — Θ(n log n) is not a lower bound of order n^2.

• T(n) = O(n log n): True (tight upper bound).