if (a <= b) { a = VECT[ b ]; } else { b = b+a; } ...può essere visto equivalentemente come la sequenza di operazioni elementari descritta sotto, assumendo che i registri
R1
e R2
siano associati rispettivamente alle
variabili a
e b
, e che la prima cella
dell'array sia all'indirizzo VECT
:
1. Confronta R1 con R2. 2. Se R1 > R2 salta al passo 5. 3. Carica in R1 il contenuto della cella all'indirizzo VECT+R2. 4. Salta al passo 6. 5. Somma R1 e R2 ponendo il risultato in R2. 6. ...Per una trattazione completa, si rimanda il lettore ai corsi di linguaggi formali e compilatori.
È possibile assegnare un costo uniforme alle operazioni elementari. In generale, ciascuna delle operazioni elementari richiede un tempo fisso e costante di esecuzione, assumendo che ogni registro e ogni cella di memoria non richieda un numero esagerato di bit (in altre parole, assumendo che tale numero cresca all'incirca con il logaritmo del numero totale di celle occupate).
In base alla condizione , uno solo tra i rami e viene eseguito. Non potendo prevedere l'esito del confronto, il costo è il seguente.
Costo: costo() + max{ costo(), costo() } tempo.
Sia il numero di volte in cui il corpo del ciclo viene eseguito, e sia la complessità di all'iterazione del ciclo for (non è detto che debba avere sempre lo stesso costo ad ogni iterazione).
Costo: .
In generale, se la variabile nel ciclo va da un'espressione a un'espressione , allora il costo di valutazione di e va aggiunto al costo suddetto.
Si noti che il ciclo for in pseudocodice incrementa automaticamente la variabile ad ogni iterazione (al contrario di Java).
Sia il numero di volte in cui la guardia del ciclo è soddisfatta. Sia la complessità di all'iterazione del ciclo while, e la complessità del corpo all'iterazione . Poiché viene valutata una volta in più rispetto a , abbiamo il seguente costo.
Costo: .
Di solito la parte difficile, rispetto alla valutazione di complessità del ciclo for, è fornire una stima del valore di .
Assumendo che il passaggio di parametri durante un'invocazione di richieda tempo costante, invocare in un punto del programma ha il seguente costo.
Costo: costo().