Vašim úkolem je určit amortizovanou složitost jednoho zavolání procedury pro inkrementaci binárního čítače.
Binární čítač reprezentuje přirozené číslo pomocí posloupnosti cifer ve dvojkové soustavě. Čítač umožňuje reprezentované číslo inkrementovat - to znamená zvýšit jeho hodnotu o jedna. Např. pokud obsahuje posloupnost cifer 1011000110 tak po inkrementaci bude obsahovat posloupnost 1011000111.
Inkrementace se provádí tak, že procházím cifry od konce a pokud čtu jedničky, tak je přepisuju na nuly, jakmile narazím na nulu tak ji zvednu na jedničku a skončím (pokud dojdu až na konec tak přidám jedničku). V nejlepším případě tedy trvá inkrementace jen konstantní čas (jako v příkladu). Může se ale stát, že čítač obsahuje např. 111111111111 což po inkrementaci dá 1000000000000, čili v nejhorším případě trvá inkrementace řádově n, kde n je počet cifer čísla.
Vašim úkolem je určit amortizovanou složitost operace inkrementace. Připomínám, že amortizovaná složitost je definovaná jako průměrný čas na vykonání jedné operace, v případě, že vykonávám víc těchto operací po sobě. Formálně: amortizovaná složitost jedné operace je limita pro k jdoucí k nekonečnu z podílu složitost k po sobě jdoucích operací lomeno k.