For each function below, let n be the least integer such that f(x) is O(xⁿ). Arrange the functions in increasing order of n:
A. f(x) = 3x³ + (log x)⁴
B. f(x) = (x⁵ + x² + 1)/(x³ + 1)
C. f(x) = (x³ + x² + 1)/(x² + 1)
D. f(x) = (x² + 5 log x)/(x² + 1)
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. D, C, B, A
Explanation
A ~ x³ (n = 3), B ~ x² (n = 2), C ~ x (n = 1), D ~ 1 (n = 0). Increasing: D, C, B, A.More Data Structures and Algorithms questions
- f(n) = a·f(n/b) + g(n) is a divide-and-conquer recurrence. Match the algorithms in List I with their recurrences in List II.List I List II…
- The height of a binary search tree built by inserting the words banana, peach, apple, pear, coconut, mango and papaya (in this order, alpha…
- How much time does an algorithm using 2⁵⁰ bit operations need if each bit operation takes 2⁻³⁸ seconds?
- A lower-triangular sparse matrix is one:
- Arrange the following prefix expressions in increasing order of their values: A. + − * 2 / 8 4 3 2 B. ↑ − * 3 3 * 4 2 5 C. + − ↑ 3 2 ↑ 2 3…
- Which of the following are true for a complete (full) binary tree? A. It always has an odd number of vertices. B. With i internal vertices,…