1テープの決定性マシン、2テープの決定性マシン、1テープの非決定性マシンの、3つのケースで繰り返し文字列（ww）を受け入れるチューリングマシンの時間計算量を把握しようとしています。
今の私の考えはそれです
1テープの決定論的マシンは、O（n ^ 2）を使用して中点を見つけ（入力の最初と最後の記号を繰り返し消して）、O（n ^ 2）を使用して前半と秒の半分を比較します（必要に応じて）文字列のn/2を通過するたびに、n / 2回前後に移動します）、
2テープTMは、中点を見つけるためにO（n ^ 2）を取り、後半を2番目のテープにコピーするためにO（n）を取り、次に2つの半分を同時に比較するためにO（n）を取ります。
非決定論的なものは中点を推測し、O（n ^ 2）を使用して2つの半分を比較します。
しかし、3つのケースすべてがO（n ^ 2）の同じ時間計算量を持つべきではないように感じるので、私の推論がどこかで間違っているのか（または私が正しいのか、問題についてよく考えているだけなのか）疑問に思いました。任意の入力をいただければ幸いです！