Trivijalni algoritam proverava svaki broj sa svakim brojem
i tu imamo slozenost O(n^2).
Ako skoro svi brojevi zadovoljavaju trazeni uslov onda je
opet slozenost O(n^2).
Ali ako malo brojeva recimo k (k << n) zadovoljava trazeni
uslov onda bi nekim efikasnijim algoritmom od trivijalnog za
te slucajeve slozenost bila manja od O(n^2), a u slucaju
kad skoro svi brojevi zadovoljavaju uslov onda bi naravno i
slozenost efikasnijeg algoritma od trivijalnog isto bila O(n^2).
Znaci problem bi bio naci algoritam koji je efikasan za
slucajeve sa malo brojeva koji zadovoljavaju uslov zadatka
i za te slucajeve ima manju slozenost od O(n^2).
[Ovu poruku je menjao farstar dana 05.09.2005. u 19:52 GMT+1]