Statement I: If f and g are two functions and f = O(g) but g ≠ o(f), we say that the growth rate of g is smaller than that of f.
Statement II: The class of all decision problems decided by a TM in exponential time is O(2ᵏ), k being a constant.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. Both Statement I and Statement II are incorrect
Explanation
If f = O(g) and g ≠ O(f), then g grows faster than f, not slower (I false). EXPTIME is the class decided in O(2^(nᵏ)) time, and the statement as written is meaningless (II false).More Data Structures and Algorithms questions
- Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: It is possible to create…
- 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³…
- 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: