Given below are two statements:

Statement I: If f and g are two functions and f = O(g) g ≠ o(f) but , 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, that is O(2k) k , being a constant. In the light of the above statements, choose the most appropriate answer from the options given below.

1. ABoth Statement I and Statement II are correct
2. BBoth Statement I and Statement II are incorrect
3. CStatement I is correct but Statement II is incorrect
4. DStatement I is incorrect but Statement II is correct 32M × 8

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 f and g grow at the same rate; g is not smaller than f, so Statement I is false. EXPTIME is decided in O(2^(nᵏ)) time — exponential in a power of n — not O(2ᵏ) for a constant k, so Statement II is false.