What is the running time (worst case) of this turing machine algorithm? The inpu
ID: 3575922 • Letter: W
Question
What is the running time (worst case) of this turing machine algorithm? The input symbols are a's and b's.
M: "On input w
1. Scan across the tape from leftmost position to the end of tape (there is a blankspace) and move tape to the left.
2. Cross off (with a X symbol) the input in current cell.
3. Move tape head to the end of the tape.
4. Write the corresponding input from previous cell that was cross off and move tape head to the neart X and move the tape head left one position.
5. If there are a's or b's left on the leftside of the tape (before X's) go back to stage 2 and repeat until there are no a's or b's left without being crossed.
6. Scan tape for all X's and overwrite them with the blank symbol (erase them) leaving the reversed string. ACCEPT."
I think this algorithm the run time (overall) is O(n^3). Because stage 1 takes O(n). From stage 2 to stage 5 we have a loop and I think this loop goes for O(n^2). Each individual stage inside the loop (2,3) are O(n) and stage 6 takes O(n).
So when computing the run time I have something like this:
O(n) + O(n^2)[O(n)+O(n)] + O(n)
= O(n) + O(n^2)[2 O(n)] + O(n)
= O(n) + O(n^3) + O(n) = O(n^3)
Am I correct? Does the loop indeed iterate n^2 times in the worst case? I think so because it has to compare each a or b, cross it off and copy it to the empty cell in the tape. Please help. :)
Explanation / Answer
Yes, in the worst case the running time will be O(n2).
Explaination:
It will take O(n) to once reach at the end of tape. //stage 1
Then it will take O(n2) to take the current input, cross it, and go the the end of tape to copy it and coming back to the left most X. //stage 2-5
Then just a scan will be left which can be done in O(n). //stage 6
Hence,the total running time will be O(n)+O(n2)+O(n)= O(n2).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.