Assume that f(n), g(n) and h(n) are asymptotically positive. Which of the following is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))
Explanation
Each asymptotic relation is transitive, so o and o give o (C). A and B mix different relations and are false. D also follows, since ω implies Ω, but C is the direct transitivity property the question intends.More Data Structures and Algorithms questions
- The solution of the recurrence relation T(n) = 3T(n/4) + n log n is
- The number of nodes of height h in any n-element heap is at most
- Consider a B-tree of height h and minimum degree t ≥ 2 that contains n keys, n ≥ 1. Which of the following is correct?
- Which algorithm design approach is used in the quick sort algorithm?
- Consider a hash table of size 11 that uses open addressing with linear probing, with h(k) = k mod 11. Records with keys 43, 36, 92, 87, 11,…
- Consider the traversals of a tree: Preorder → ABCEIFJDGHKL Inorder → EICFJBGDKHLA Which of the following is the correct postorder traversal?