Contatore Binario con Increment

Sia un array di k Bit.

1101011 1101100

Increment(A)
i = 0
while (i<k) && A[i]=1 do:
	A[i] = 0
	i++
if (i<k) then:
	A[i] = 1

Costo di un’incremento: Costo di incrementi =

Anche in questo caso c’è un’analisi sovrabbondante.

Il contatore è inizialmente nullo a meno che non venga specificato altrimenti

Contatore Binario con Aggregazione

Supponiamo che esistano due operazioni:

E che il contatore sia inizialmente nullo.

Notiamo che su operazioni di tipo :

Otteniamo: Otteniamo una serie geometrica di ragione

Abbiamo tolto il floor ponendo la serie senza floor maggiore o uguale a quella con il floor, e sostituito k-1 con per maggiorare. Otteniamo

Poniamo:

Un’operazione di altro non è che , per cui:

, La differenza è non negativa per ogni istante di esecuzione.

Per cui vale: , e riotteniamo lo stesso risultato del metodo dell’aggregazione:

Ossia incrementi in tempo , indipendentemente da (il numero di bit)

Sia , e .

Stiamo rispettando la disuguaglianza .

Di nuovo, il costo ammortizzato è:

Si ha perciò:

Nota Bene:

Pertanto:

Da cui:

Poniamo come prima , ma stavolta .

Otteniamo il valore del costo reale:

Dove k è il numero di bit nel contatore.

Se , allora e quindi .

Troveremo che il numero di bit k si palesa anche utilizzando negli altri metodi, nel caso di contatore non nullo.