Consider the following functions: f(n) = 3n√n, g(n) = 2√n log₂ n, h(n) = n!. Which of the following is true?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. f(n) is O(g(n))
Explanation
g(n) = 2√n log n = n√n, so f(n) = 3·g(n) and f is O(g) (and g is O(f)). n! grows faster than n√n, so h is not O(f) or O(g).More Data Structures and Algorithms questions
- 2-3-4 trees are B-trees of order 4. They are isometric to ______ trees.
- Consider the following statements about the heap sort algorithm: A. The MAX-HEAPIFY procedure, which runs in O(lg n) time, is the key to ma…
- Match List I with List IIList I List II A. Parallel FFT I. Θ(n²) B. Iterative FFT II. Θ(n) C. Evaluation of polynomial at n points by Horne…
- 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…
- 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…