Given below are two statements:
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, that is O(2^k), k being a constant.
In the light of the above statements, choose the most appropriate answer from the options given below.

Question

Question

This question was previously asked in

UGC NET Computer Science (Paper 2) 17 June 2023 Official Paper

Answer 1

The correct answer is Both Statement I and Statement II are incorrect

EXPLANATION:

Statement I: This is incorrect.
- The notation f = O(g) means that the growth rate of function f is bounded by the growth rate of function g, up to a constant factor and beyond a certain point.
- If, in addition, g is not little o of f (meaning, g does not grow significantly slower than f beyond that certain point), then that doesn't bear on f growing faster than g. Instead it should mean that f does not grow faster than g and g does not grow significantly slower than f.
Statement II is incorrect.
- The class of decision problems decided by a Turing Machine (TM) in exponential time is typically denoted by EXP, and it is associated with O(2^poly(n)), where "poly(n)" represents a polynomial in the input size n.
- The statement wrongly suggests that the class is O(2^k), where k is a constant. In reality, the exponent in the exponential time complexity is a polynomial function of the input size.