Vidimo, da imamo dve gnezdeni zanki, ki imata v najslabšem primeru vsaka približno n iteracij (i gre od 0 do n - 2, nato pa gre j od i + 1 do n - 1). Tako se stavek if
izvede kvečjemu n ⋅ n = n2-krat, pri vsakem izvajanju tega stavka pa imamo konstantno mnogo osnovnih operacij (eno seštevanje, eno primerjanje itd.). Ta razmislek nam pokaže, da je število osnovnih operacij v tem postopku reda O(n2) in takšna je zato tudi časovna zahtevnost tega postopka.
Podobno lahko analiziramo tudi postopek NajdiVsoto3
:
Zunanja zanka, po i
, tudi tu izvede največ n iteracij (dejansko največ n - 1, vendar pri razmišljanju o časovni zahtevnosti takšne malenkosti niso zares pomembne).
Notranja zanka, po j
, pa zdaj izvede največ n iteracij v vseh ponovitvah zunanje zanke skupaj – torej ne n iteracij pri vsakem i, ampak n iteracij pri vseh i skupaj.
To je posledica dejstva, da se j začne pri n - 1, v vsaki iteraciji notranje zanke se zmanjša za 1, poleg tega pa j nikoli ne more pasti pod 0 (saj se celoten postopek konča, ko postane j ≤ i).
Tako se torej tudi tisti del funkcije, ki je vgnezden v obeh zankah (tam imamo en stavek if
in prireditev j -= 1
), izvede največ O(n)-krat; enako pa seveda velja tudi za tiste vrstice, ki so vgnezdene le v zunanji zanki, ne pa v notranji. Tako vidimo, da je časovna zahtevnost tega postopka le O(n), ne pa na primer O(n2) kot pri prejšnjem postopku.