Data Structures and Algorithms MCQ - Performance Analysis of Algorithms and Recurrences

41 Let f (n), g(n) and h(n) be functions defined for positive integers such that f (n) = O(g(n), g(n)) ≠ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statements is FALSE?

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

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)
2⁴ – 3 – 2 = 16 – 3 – 2 = 11
so option (A) is true.

43 The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be

The time complexity of computing the transitive closure of binary relation on a set of n elements is O (n³).

44 Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + √n for n ≥ 2 and T(1) = 1. Which of the following statements is TRUE?

T(n) = 2T(n/2) + √n
Apply master’s method
n^log₂² ⇒ n > √n
So T(n) = Θ(n)

45 Suppose T(n) = 2T (n/2) + n, T(0) = T(l) = 1 Which one of the following is FALSE?

T (n) = 2 T (n/2) + n
Apply masters method.
n^log₂² ⇒ n ≅ n
So T (n) = O (nlogn)
Now growth rate of n² and nlogn is greater than and equal to nlogn, thus (c) is false T (n) = Ω represent lower growth (n²)