adplus-dvertising
frame-decoration

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

Answer: (c).O(n^2f^2)

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

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

Similar Questions

Discover Related MCQs

Q. Which among the following is false?

If f=O(h) and g=O(k) for f,g,h,k:N->N, then

Q. Which of the following is not correct for ZPP?

Q. ZPP is based on ________

Q. ZPP is exactly equal to the ____________of the classes RP and co-RP.

Q. Suppose we have a las vegas algorithm C to prove ZPP is contained in RP and co-RP. Run C for double its expected running time.
By Markov’s inequality, the chance that it will answer before we stop is:

Q. State true or false:
Statement: ZPP is closed under complement function.

Q. Which of the following technique is used to find whether a natural language isnt recursive ennumerable?

Q. Diagonalization can be useful in:

Q. Which of the following are undecidable problems?

Q. Which of the following are incorrect options?

Q. If a problem has an algorithm to answer it, we call it _________

Q. Which of the following are decidable problems?

Q. Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}

Q. Statement: If L id R.E., L^c needs to be R.E. Is it correct?

Q. Which of the following is true for The Halting problem?

Q. With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.

Q. With reference to enumeration of binary strings, the conversion of binary strings to integer is possible by treating the resulting string as a base ____ integer.

Q. The decision problem is the function from string to ______________

Q. A language L is said to be ____________ if there is a turing machine M such that L(M)=L and M halts at every point.

Q. Which aong the following are undecidable theories?