Let f(n) and g(n) be asymptotically positive functions.
Statement I: f(n) ≥ 1 and f(n) = O(g(n)) ⇒ g(n) = Ω(f(n)).
Statement II: f(n) = O(g(n)) ⇒ lg(f(n)) = O(lg(g(n))), where lg(g(n)) ≥ 1 and f(n) ≥ 1 for all sufficiently large n.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. Both Statement I and Statement II are correct
Explanation
I is transpose symmetry: f = O(g) iff g = Ω(f). II: f ≤ c·g gives lg f ≤ lg c + lg g ≤ (lg c + 1) lg g when lg g ≥ 1, so lg f = O(lg g). Both are correct (CLRS problem 3-4).More Data Structures and Algorithms questions
- Consider the following statements: A. If some NP-complete problem is in P, then P = NP. B. TSP is in NP. C. SAT is in NP. D. The Hamiltonia…
- A B-tree used as an index for a large database table has four levels including the root node. If a new key is inserted into this index, the…
- Suppose a circular queue of capacity n − 1 elements is implemented with an array of n elements. Insertion and deletion use REAR and FRONT a…
- Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: AVL trees are more balan…
- Consider a hash table of size 7 with starting index 0 and hash function (6x + 3) mod 4. Assuming the table is initially empty, which of the…
- Match List I with List IIList I List II A. Running time of a straightforward recursive method to compute the nth Fibonacci number Fₙ I. O(n…