Amortisoitu aika on tapa ilmaista aikakompleksisuus silloin, kun algoritmilla on erittäin huono aikakompleksisuus vain silloin tällöin sen aikakompleksisuuden ohella, joka tapahtuu suurimman osan ajasta. Hyvä esimerkki olisi ArrayList, joka on tietorakenne, joka sisältää joukon ja jota voidaan laajentaa. Toinen määritelmä Stack Overflow’sta on keskimääräinen aika, joka kuluu per operaatio, jos teet monia operaatioita.
Kun ArrayList saavuttaa siinä olevan array-kapasiteetin, niin se luo uuden array:n, jonka koko on kaksinkertainen vanhaan array:iin verrattuna, ja kopioi kaikki vanhan array:n kohteet uuteen array:iin. ArrayListissä on kaksi aikakompleksisuutta; toinen on O(1) ja toinen on O(n).
Kun siinä oleva array ei ole saavuttanut kapasiteettiaan ja siinä on vielä tarpeeksi tilaa lisätä kohteita
Tällöin kohteen lisäämiseksi arrayyn riittää, että asetamme kohteen viimeisen kohteen jälkeen. Meillä on vielä tilaa lisätä kohteita.
Kun siinä oleva array on saavuttanut kapasiteettinsa ja sen on luotava itsensä uudestaan kaksinkertaistuneella koolla
Matriisi on saavuttanut kapasiteettinsa eikä meillä ole enää vapaita paikkoja. Silloin meidän on luotava kokonaan uusi array kaksinkertaistetulla koolla. Ja sitten kopioida vanhan joukon kohteet uuteen, mikä vie aikaa O(n), jossa n on vanhan joukon kapasiteetti ja pahin tapaus.
Kun ilmaisemme näitä kahta aikakompleksisuutta, niin tässä kohtaa käytetään jaksotettua aikaa. Se tekee sen, että voimme kuvata, että pahin tapaus tapahtuu aina silloin tällöin, kun sisäinen array saavuttaa kapasiteettinsa.
Mutta kerran se tapahtuu, se ei tapahdu uudelleen niin pitkään aikaan, että kustannus on ”kuoletettu”. Jos sisäisen matriisin kapasiteetti alkaa 1:llä, niin kapasiteetit ovat 1, 2, 4, 8, 16… X, kun se saavuttaa kapasiteetin ja kaksinkertaistuu. Uuteen arrayyn kopiointiin tarvitaan 1, 2, 4, 8 16… X elementtiä riippuen saavutetusta kapasiteetista. Ajan monimutkaisuus on siis 1 + 2 + 4 + 8 + 16 +… X. Jos ajatellaan X:stä, tämä on X + X/2 + X/4 + X/8… + 1 = 2X noin. Eli toisin sanoen tarkasti,
Sisällyttämiseen kuluu aikaa O(2X), kun X:n kapasiteetti on saavutettu, ja amortisoitunut aika jokaiselle lisäykselle on O(1).
