"végigtologatja az egész szalagot"
Akkor lehet, hogy nem sikerült elég jól leírnom, mire gondoltam. Tologatás nincs a duplázó szakaszban, csak egy n hosszú kifejezés átírása (x^n c^n) alakúra. Ez pedig szerintem legfeljebb négyzetes (ha minden esetben, mikor az első c-t keresi egy x kiírása után, visszamenne #-ig, azon jobban látszik, miért), és a második (az ellenőrző) szakasz is az.
Ettől függetlenül persze a tiéd hatékonyabb, de nem nagyságrendileg.