časovna zahtevnost algoritma

Imaš dve zanki eno znotraj druge. Si prepričan, da je O(n) sploh opcija?

Zanki sta vgnezdeni. O(n)^2, zakaj je tako je lepo razloženo na spodnji povezavi.
http://stackoverflow.com/questions/5267...

hvala za odgovore (:

Če si predstavljaš, kaj ti dve zanki delata ... gresta skozi elemente n*n tabele. S tem da pogledaš samo elemente, ki imajo drugo koordinato (y) manj od prve (i). Torej dobiš zgornji desni trikotnik matrike:

o	x	x	...	x
o	o	x	...	x
o	o	o	...	x
			...
o	o	o	...	o

Torej nisi pogledal n elementov na diagonali, od ostalih n*n-n=n(n-1) pa si pogledal natanko polovico (enega od dveh trikotnikov). Torej si pogledal n(n-1)/2 elementov.