Turing machine closed

Question

Comments

https://gateoverflow.in/113193/ace-test-series

---

option c ?

let say a multi-tape tm which has to recognize xⁿyⁿ which will take atleast n comparison. now if we need to construct tm with single tap it would take at most  n * n-1 * n-2 * .......*1 = n! comparison. 

Answer 1

option a should be answer

example if we  use multi tape turing machine taken example of a^nb^n then time complexity is O(n) as we can maintain two tape and contain of one tape copy to another tape and matching a's of one tape with b's of another tape in linear time.

but if we use single tape turing machine of above language eg: aaaabbbb if we have to match a's with b's  then 4 times we have to move forward and backwards and comparison {n+n-1+n-2.....1} which is O(n^2) therefore time complexity increases by double.