У неким ситуацијама се извесне операције понављају пуно пута током извршавања програма. У многим ситуацијама можемо да допустимо да појединачно извршавање неке операције траје и мало дуже, ако смо сигурни да више извршавања те операције у збиру неће трајати предуго (што се дешава ако постоји довољно извршавања те операције која ће трајати кратко). Анализа укупне дужине трајања већег броја операција назива се амортизована анализа сложености. Амортизована цена извршавања \(n\) операција подразумева количник укупног броја корака током њиховог извршавања и броја \(n\). Нагласимо да се овде рачуна просечно време низа операција које се извршавају узастопно, што је прилично различито од просечне сложености где се анализира просечан број корака потребних за извршавање једне операције на свим могућим улазима дате димензије. Илуструјмо анализу амортизоване сложености на једном важном примеру.
Једна од најчешће употребљаваних структура података је динамички низ. Када у низу нема довољно простора да се смести наредни елемент, низ се динамички реалоцира. У најгорем случају ово подразумева копирање старог садржаја низа на нову локацију, што је операција сложености \(O(m)\), где је \(m\) број елемената до тада уписаних у низ. Поставља се питање како приликом реалокација одређивати број елемената проширеног низа. Аритметичка стратегија подразумева да је нова величина низа увек за неко фиксно \(k\) већа од од тренутне, а геометријска да је нова величина низа неко фиксно \(q\) пута већа од тренутне.
Једна стратегија реалокације може бити аритметичка и она подразумева да се кренувши од празног низа приликом сваке реалокације величина низа повећа за неки фиксан број \(k\) (ништа се суштински не би променило у анализи и да је иницијални капацитет уместо \(0\) неки број \(m_0\)). Претпоставимо да \(n\) пута извршавамо операцију додавања елемента на крај низа (тј. да у низ убацујемо \(n\) елемената) и избројмо колико је пута током тога потребно извршити корак физичког уписа елемента у низ (тај корак је обично најспорији). Тај корак ће се вршити приликом уписа нових елемената у низ, али и приликом померања постојећих елемената на нове меморијске локације током реалокације низа (претпостављамо најгори случај у ком је приликом сваке реалокације потребно премештати све елементе низа).
Поступак се наставља све док се не упише \(n\)-ти елемент. Дакле, број корака физичког уписа је једнак \(k + k + k + 2k + k + 3k + \ldots\), при чему се у овом збиру наизменично смењују операције уписивања нових и преписивања старих елемената (уписујемо \(k\), па преписујемо \(k\), па уписујемо \(k\), па преписујемо \(2k\) итд.). Да би се сместило \(n\) елемената, алокацију простора је потребно вршити око \(n/k\) пута. Једноставности, ради, претпостављамо да је \(n\) дељив са \(k\). Дакле, \(\frac{n}{k}\) пута смо уписали по \(k\) елемената низа (чиме смо их уписали укупно \(n\), попунивши цео алоцирани простор), а померали смо редом \(k\) елемената, затим \(2k\), итд. све до последње реалокације у којој смо преписали \((\frac{n}{k} - 1)k\) елемената. Зато ће укупан број корака физичког уписа у низ бити отприлике једнак:
\[\frac{n}{k}k + (1 + 2 + \ldots + \left(\frac{n}{k}-1\right))\cdot k = n + \frac{\frac{n}{k}(\frac{n}{k} - 1)}{2}\cdot k = \frac{n^2}{2k} + \frac{n}{2}\]
Дакле, укупан број корака физичког уписа је асимптотски једнак \(\frac{n^2}{2k}\) тј. \(O(n^2)\) и стога је амортизована цена једне операције додавања елемента на крај низа асимптотски једнака \(\frac{n}{2k}\), што је \(O(n)\). Додуше, константе уз \(n\) има малу вредност (што је веће \(k\), то је реалокација мање, па је амортизована цена операције додавања на крај низа мања, али се цена плаћа кроз веће заузеће меморије и мању попуњеност алоцираног простора).
Друга стратегија може бити геометријска и она подразумева да се сваки пут величина низа повећа \(q\) пута за неки фактор \(q > 1\). Претпоставимо да је почетна величина низа \(m_0\).
Поступак се даље наставља по истом принципу. Дакле, укупан број корака физичког уписа елемента у низ једнак је
\[m_0 + m_0 + (qm_0 - m_0) + qm_0 + (q^2m_0 - qm_0) + \ldots = m_0 + qm_0 + q^2m_0 + \ldots\]
После \(r\) реалокација и попуњавања целог алоцираног простора који је тада величине \(q^rm_0\), укупан број корака уписа у низ једнак је
\[m_0 (1 + \ldots + q^r) = m_0 \frac{q^{r+1}-1}{q-1}.\]
Последњи сабирак \(q^rm_0\) долази од уписа нових елемената, а сви претходни сабирци долазе од преписивања елемената на друге локације приликом реалокације.
Ако претпоставимо да је цео низ попуњен после \(r\) реалокација, тј. да је \(n = m_0q^r\), онда је укупан број корака физичког уписа потребних за попуњавање динамичког низа са \(n\) елемената једнак
\[m_0\frac{q\frac{n}{m_0}-1}{q-1} = \frac{qn-m_0}{q-1}.\]
Асимптотски је, дакле, укупна цена извођења свих операција једнака \(O(n)\), а амортизована цена извођења једне операције додавања елемента на крај оваквог низ је \(O(1)\). Константан фактор једнак је \(\frac{q}{q-1}\) и он је све мањи како \(q\) расте. Заиста, са повећањем \(q\) врши се све мање реалокација, али се цена плаћа већим ангажовањем меморије тј. мањом попуњеношћу низа.
Амортизована анализа сложености нам показује да са становишта времена извршавања геометријска стратегија реалокације даје значајно боље резултате него аритметичка.