GATE CS 2005 – Question 35

Multiple choice 2 marks Question 35 2005

Question 35

MCQ 2 marks · −0.66 Algorithms

Suppose \(T(n) = 2T(n/2) + n\), with \(T(0) = T(1) = 1\).

Which one of the following is FALSE?

A \(T(n) = O(n^2)\) B \(T(n) = \Theta(n \log n)\) C \(T(n) = \Omega(n^2)\) D \(T(n) = O(n \log n)\)

Answers and explanations are free — they just need an account.

GATE CS — Computer Science & IT 2005 Algorithms

Source: GATE 2005 Computer Science and Engineering, Q35 (question number approximate)