The running time T (n), where 'n' is input size of a recursive algorithm, is given as <br /> T (n) = c + T (n - 1), if n > 1 <br /> = d, if n ≤1 <br />The order of the algorithm is

www.ThinkITI.com

Home
MCQ
Search
Free Apps
Important
Study Groups
Contact Us
Policy

Home
MCQ
Objective Questions
Engineering
Computer Science
Computer Science Set-1
Theory of Computation
82

Theory of Computation MCQ with Answers

82) The running time T (n), where 'n' is input size of a recursive algorithm, is given as
T (n) = c + T (n - 1), if n > 1
= d, if n ≤1
The order of the algorithm is

Answer is:

n

Theory of Computation MCQ with Answers

For more MCQ's Click Here

83) Next move function δ of a Turing machine M = (Q, Σ ,Γ,δ, q0, B, F) is a mapping

δ: Q xΣ --> Q xΓ

δ: Q xΓ---> Q xΣx {L, R}

δ: Q xΣ--->Q xΓx {L, R}

δ: Q xΓ--->Q xΓx {L, R}

Answer is:

δ: Q xΓ--->Q xΓx {L, R}

84) If L can be recognized by a TM T with a doubly infinite tape, and τt = f, then L can be recognized by an ordinary TM with time complexity

O(f)

o(f)

O(h)

Answer is:

O(f)

85) Number of states of the FSM required to simulate behaviour of a computer with a memory capable of storing "m" words, each of length 'n'

m x 2n

2mn

2m+n

all of these

Answer is:

2mn

86) An FSM with

1 stack is more powerful than an FSM with no stack

2 stacks is more powerful than a FSM with 1 stack

both 1) 1 stack is more powerful than an FSM with no stack and 2) 2 stacks is more powerful than a FSM with 1 stack

None of these

Answer is:

both 1) 1 stack is more powerful than an FSM with no stack and 2) 2 stacks is more powerful than a FSM with 1 stack

Theory of Computation MCQ with Answers

For more MCQ's Click Here

82) The running time T (n), where 'n' is input size of a recursive algorithm, is given as T (n) = c + T (n - 1), if n > 1 = d, if n ≤1 The order of the algorithm is

n

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

83) Next move function δ of a Turing machine M = (Q, Σ ,Γ,δ, q0, B, F) is a mapping

δ: Q xΓ--->Q xΓx {L, R}

84) If L can be recognized by a TM T with a doubly infinite tape, and τt = f, then L can be recognized by an ordinary TM with time complexity

O(f)

85) Number of states of the FSM required to simulate behaviour of a computer with a memory capable of storing "m" words, each of length 'n'

2mn

86) An FSM with

both 1) 1 stack is more powerful than an FSM with no stack and 2) 2 stacks is more powerful than a FSM with 1 stack

Theory of Computation MCQ with Answers

82) The running time T (n), where 'n' is input size of a recursive algorithm, is given as
T (n) = c + T (n - 1), if n > 1
= d, if n ≤1
The order of the algorithm is