Question

Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)

(a) O(nf)

(b) O(n+f)

(c) O(n^2f^2)

(d) None of the mentioned

The question was asked by my school teacher while I was bunking the class.

Origin of the question is Class RP and ZPP,Complexity in chapter Other Classes Of Problems of Automata Theory

Answer 1

Right answer is (c) O(n^2f^2)

Explanation: Using the encoding function, it is possible to show that if the function f is a step counting function, then the function Cn^2(f(n))^2 is the total number of moves required.