turing-gépnél nincs olyan, hogy "átírod" hosszabbra, ez nem láncolt lista, hogy csak úgy közészúrt valamit, csak celláid vannak. ha közé akarsz valamit beszúrni, akkor minden utána lévő cellát egyesével át kell másolgatni a jobbra levőbe, nyilván a végénél kezdve. jelen esetben ezt n/4-szer kellene végigzongorázni, szóval nagyjából (n/4)*(n/2), ha jól számolom, magyarul (n^2)/2, és akkor még semmit nem ellenőriztünk, csak csinosítottunk az inputszón.
a kérdés már csak az, hogy az ellenőrzés az valóban négyzetes-e, amit még át kell gondoljak. ha az, akkor nagyságrendileg tényleg nem növeli, csak mondjuk (hasraütésre) 2-szeres lesz a lefutási idő. ha nem négyzetes, akkor viszont ront rajta.