Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
- Option : D
- Explanation : Given, f (n) = O (g (n)) g (n) ≠ O (f (n)) g (n) = O (h (n)) h (n) = O (g (n)) So conclusion is f (n) < g (n) = h (n) { in terms of growth rate} So (A) f (n) + g (n) = O (h(n) + h (n)) is true. (B) f (n) = O (h (n)) is true. (C) h (n) ≠ O (f (n)) is true. (D) f (n) * h(n) ≠ O (g(n) * h (n) is false.
42. The recurrence equation: T(1) = 1 T(n) = 2T(n–l) + n, n ≥ 2 evaluates to
- Option : A
- Explanation : T (1) = 1 T (n) = 2 T (n–1) + n , n ≥ 2 if n = 2 then T (2) = 2 T (1) + 2 = 2 × 1 + 2 = 4 if n = 3 then T (3) = 2 T (2) + 3 = 2* 4 + 3 = 11 Put n = 3 in option (A) 24 – 3 – 2 = 16 – 3 – 2 = 11 so option (A) is true.
- Option : D
- Explanation : The time complexity of computing the transitive closure of binary relation on a set of n elements is O (n3).
45. 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)
