PA of Algorithms Q45
0. Suppose T(n) = 2T (n/2) + n, T(0) = T(l) = 1 Which one of the following is FALSE?
- Option : C
- Explanation : T (n) = 2 T (n/2) + n Apply masters method. nlog22 ⇒ n ≅ n So T (n) = O (nlogn) Now growth rate of n2 and nlogn is greater than and equal to nlogn, thus (c) is false T (n) = Ω represent lower growth (n2)
