slozenost petlje? (zadatak)

[Gost]

da li bi mi mogao netko staviti neki jednostavni primjer za petlje slozenosti
1. O(lg_n)
2. O(lglg_n)
3. O(nlg_n)

bio bih jako zahvalan?

[matmih]

[Gost]

jel moze objesnjenje ovog 3.(nlgn)?

jer nije mi bas najjasnije:

dobijem za bilo koji n da je slozenost:

(n+[n/2]+[n/2^2]+[n/2^4]+...+[n/2^lgn]) = n(?-zasto je ta suma lgn?)

p.s. [x]-mi je najvece cijelo

[vsego]

Krivo gledas: unutarnja petlja ne ovisi o i, nego se uvijek vrti n puta. Vanjska se vrti puta, pa je to ukupno ono .

Editirah kod, da bude pregledniji, pa je sada mozda jasnije.

_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.

[Gost]

zahvaljujem, pomoglo mi je..