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

GATE · 2005 · CS

1. A.

   T(n) = O(n2)

2. B.

   T(n) = θ(n log n)

3. C.

   T(n) = Ω(n2)

4. D.

   T(n) = O(n log n)

Attempted by 288 students.