Прикажимо сада кроз неколико примера анализу сложености итеративно имплементираних алгоритама. Иако нећемо посматрати решења конкретних задатака, потрудићемо се да у примерима покријемо облике петљи који се јављају у великом броју конкретних алгоритама и решења конкретних задатака.
У примерима петљи који следе, претпоставља се да кôд у телу петљи који није приказан не утиче на бројачке променљиве и не мења границе петљи.
for (int i = 0; i < n; i++)
// kod slozenosti O(1)Сложеност претходне петље је \(O(n)\).
for (int i = m; i < n; i++)
// kod slozenosti O(1)Сложеност претходне петље је \(O(n-m)\).
for (int i = 0; i < n; i += 2)
// kod slozenosti O(1)Сложеност претходне петље је \(O(n)\). Пошто се петља извршава за парне вредности бројачке променљиве, тело петље се извршава око \(\frac{n}{2}\) пута и константни фактор је \(\frac{1}{2}\), али је сложеност и даље линеарна.
for (int i = 0, j = n-1; i < j; i++, j--)
// kod slozenosti O(1)Сложеност претходне петље је \(O(n)\). Показивачи се сусрећу приближно на средини опсега, а тело петље се извршава око \(\frac{n}{2}\) пута.
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(mn)\). Заиста, спољашња петља се извршава \(m\), а у њеном телу се унутрашња петља извршава \(n\) пута, па се тело унутрашње петље изврши тачно \(mn\) пута.
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(n^2)\). Заиста, спољашња петља се извршава \(n\), а у њеном телу се унутрашња петља извршава \(n\) пута, па се тело унутрашње петље изврши тачно \(n^2\) пута.
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(n^2)\). Број извршавања тела унутрашње петље је \((n-1) + (n-2) + \ldots + 2 + 1\), што је једнако \(\frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n\). Константни фактор је \(\frac{1}{2}\), али је сложеност квадратна. До истог резултата можемо доћи ако схватимо да у сваком кораку унутрашње петље пар бројача одређује једну комбинацију бројева од \(0\) до \(n-1\). Зато број извршавања тела одговара броју двочланих комбинација скупа од \(n\) елемената, што је једнако \(\binom{n}{2} = \frac{n(n-1)}{2}\).
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; j++)
// kod slozenosti O(1)Сложеност претходних петљи је прилично очигледно \(O(n^3)\).
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
for (int k = j+1; k < n; j++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(n^3)\). Најлакши начин да се ово закључи је да се примети да сваком извршавању тела одговара једна трочлана комбинација елемената скупа \(0\), \(\ldots\), \(n-1\). Пошто трочланих комбинација има \(\binom{n}{3} = \frac{n(n-1)(n-2)}{3\cdot 2 \cdot 1}\), сложеност је кубна, а константни фактор је \(\frac{1}{6}\).
for (int i = 0; i < m; i++)
// kod slozenosti O(1)
for (int i = 0; i < n; i++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(m+n)\). Наиме, тело прве петља се изврши \(m\) пута, а затим тело друге петље \(n\) пута, па се тела обе петље укупно изврше \(m+n\) пута.
for (int i = 0; i < n; i++)
// kod slozenosti O(1)
for (int i = 0; i < n; i++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(n)\). Наиме, тело прве петље се изврши \(n\) пута, а затим тело друге \(n\) пута, па се тела обе петље укупно изврше \(2n\) пута, но то је \(O(n)\).
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
// kod slozenosti O(1)
for (int i = 0; i < n; i++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(n^2)\). Наиме, тело угнежђених петљи се изврши \(\frac{n(n+1)}{2}\) пута, а затим тело друге петље \(n\) пута, што је заправо занемариво мало у односу на број извршавања тела угнежђених петљи. Дакле, први део кода апсолутно доминира временом извршавања и сложеност је \(O(n^2)\).
Могло би се помислити да број угнежђених петљи одговара степену полинома, али то није увек случај.
for (int i = 1; i*i <= n; i++)
// kod slozenosti O(1)Иако садржи једну петљу, сложеност претходног кода није \(O(n)\), већ \(O(\sqrt{n})\). Наиме, петља се извршава све док је \(i^2 \leq n\) тј. док је \(i \leq \sqrt{n}\).
for (int i = 1; i < n; i *= 2)
// kod slozenosti O(1)Иако претходни код садржи петљу, његова сложеност је \(O(\log{n})\), јер се вредност променљиве i дуплира у сваком кораку, све док не престигне граничну вредност \(n\).
for (int i = 0; i < 10; i++)
// kod slozenosti O(1)Сложеност претходног кода је \(O(1)\). Иако је присутна петља, број њених извршавања је увек 10 и не зависи ни од једног параметара, па га можемо сматрати малом константом.
for (int i = 1; i < n; i++)
for (int j = 1; j < i; j *= 2)
// kod slozenosti O(1)Сложеност претходног кода је \(O(n \log{n})\). Сложеност унутрашње петље, за свако конкретно i је \(O(\log{i})\), па је укупна сложеност отприлике једнака \(\log{1} + \log{2} + \ldots + \log{n}\), а за ово се може показати да је \(O(n \log{n})\) (јасно је да је израз мањи или једнак \(n \log{n}\) јер је сваки сабирак мањи или једнак \(\log{n}\), међутим, може се показати и да је збир већи или једнак од \(\frac{n}{2}\log{\frac{n}{2}}\) (што је такође \(\Theta(n \log{n})\)), занемаривањем првих \(\frac{n}{2}\) сабирака, након чега остају само сабирци који су већи или једнаки \(\log{\frac{n}{2}}\)).
for (int i = n; i >= 1; i /= 2)
for (int j = 1; j < i; j++)
// kod slozenosti O(1)Сложеност претходног кода је \(O(n)\). Наиме, број извршавања унутрашње петље је \(n + \frac{n}{2} + \frac{n}{4} + \ldots\), за шта се лако може показати да је одозго ограничено са \(2n\).
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n && P(a[j]); j++)
// kod slozenosti O(1)
// kod slozenosti O(1)
i = j;
}Овакав код се може срести у алгоритмима у којима се анализирају све серије узастопних елемената низа који задовољавају неко својство P (на пример, коришћењем петљи овог облика можемо пронаћи најдужу серију узастопних парних елемената).
Иако постоје угнежђене петље, сложеност претходног кода је \(O(n)\). Број извршавања унутрашње петље зависи од стања низа a, па не знамо унапред ни колико пута ће та петља бити покренута нити колико ће се пута њено тело извршити при сваком покретању. Међутим, да бисмо одредили укупну сложеност целог кода, то нам није ни потребно. Можемо извршити амортизовану анализу и израчунати укупан број извршавања тела унутрашње петље. Кључни детаљ је то што унутрашња петља креће од текуће вредности спољашње бројачке променљиве, док спољашња бројачка променљива након унутрашње петље наставља тамо где се унутрашња петља завршила. Зато при сваком пролазу кроз тело унутрашње петље променљива j има строго вредност већу него при сваком претходном пролазу, што се може десити највише \(n\) пута.
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && P[j]) {
// kod slozenosti O(1)
j++;
}
// kod slozenosti O(1)
}Иако постоје угнежђене петље, сложеност претходне петље је \(O(n)\). Кључни детаљ је то што унутрашња петља нема иницијализацију променљиве j на нулу и бројач ј у унутрашњој петљи се све време само увећава (исто као и бројач i у спољашњој петљи). Укупан број корака је стога ограничен са \(2n\).
int l = 0, d = n-1;
while (l < d) {
do l++; while (l < d && P(a[l]));
do d--; while (l < d && Q(a[d]));
if (l < d)
// kod slozenosti O(1)
}Сличан кôд се, на пример, може срести у алгоритму партиционисања низа. И претходни алгоритам је сложености \(O(n)\) иако и он садржи угнежђене петље. То поново можемо утврдити амортизованом анализом (јер не знамо појединачни број извршавања унутрашњих петљи, али можемо лако проценити укупан корака који се у њима направи). Наиме, променљива l се само увећава кренувши од почетка, а d се само смањује кренувши од краја низа, док се не сусретну, што ће се десити у највише \(n\) корака.
Дакле, иако нам у већини случајева угнежђеност петљи описује сложеност алгоритма, треба бити обазрив и код анализирати пажљивије, да се сложеност не би преценила.