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 mentionedThe 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

Let f: N->N be a step counting function. Then for some constant C, Tim

1.	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 mentionedThe 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» 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.

Discussion

No Comment Found

Related InterviewSolutions

Which of the following is not correct for ZPP?(a) zero error probabalistic polynomial time(b) it runs in non-polynomial time(c) it returns an answer yes, no or do not know(d) none of the mentionedI have been asked this question in semester exam.This is a very interesting question from Class RP and ZPP,Complexity topic in chapter Other Classes Of Problems of Automata Theory
Which of the following are basic complexity classes for a function f:N->N?(a) Ntime(f)(b) Nspace(f)(c) Space(f)(d) All of the mentionedI have been asked this question in exam.Query is from Class RP and ZPP,Complexity in section Other Classes Of Problems of Automata Theory
Which of the following algorithms are probably correct as well as fast?(a) Las Vegas Algorithm(b) Monte Carlo Algorithm(c) Atlantic City Algorithm(d) All of the mentionedI had been asked this question in an internship interview.Enquiry is from Randomized Algorithm topic in section Other Classes Of Problems of Automata Theory
A function f is called __________ if there exists a TM T so that for any n and any input string of length n, T halts in exactly f(n) moves.(a) Step function(b) Step counting function(c) Inplace functions(d) None of the mentionedI had been asked this question in an online interview.Question is taken from Class RP and ZPP,Complexity in division Other Classes Of Problems of Automata Theory
State true or false:Statement: A turing machine has the capability of using randomly ‘generated’ numbers.(a) Statement: A turing machine has the capability of using randomly ‘generated’ numbers.(b) true(c) falseThis question was addressed to me at a job interview.This key question is from Randomized Algorithm topic in chapter Other Classes Of Problems of Automata Theory
Which of the following are probalistic algorithms?(a) Las Vegas Algorithm(b) Monte Carlo Algorithm(c) Atlantic City Algorithm(d) All of the mentionedThe question was asked in an online quiz.This interesting question is from Randomized Algorithm topic in division Other Classes Of Problems of Automata Theory
Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.(a) time(b) space(c) both time and space(d) none of the mentionedThis question was addressed to me in an internship interview.The query is from PSPACE topic in division Other Classes Of Problems of Automata Theory
Which among the following is smallest for n=50(a) 2n2(b) n2+3n+7(c) n3(d) 2nThis question was posed to me at a job interview.Enquiry is from Class RP and ZPP,Complexity topic in portion Other Classes Of Problems of Automata Theory
A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.(a) worst case(b) best case(c) average case(d) none of the mentionedThis question was posed to me in an online interview.The query is from Randomized Algorithm in portion Other Classes Of Problems of Automata Theory
Complement of all the problems in PSPACE is ________(a) PSPACE(b) NL(c) P(d) All of the mentionedI had been asked this question during an interview for a job.I need to ask this question from PSPACE in division Other Classes Of Problems of Automata Theory

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment