Štetje osnovnih operacij

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:

Izvedi Počisti



					

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.