Pretpostavimo da je n(=broj mogucnosti za trenutak) jako veliko, tj. da daleko premasuje opsege ugradjenih tipova, pa da se mora koristiti aritmetika za racunanje u proizvoljnoj tacnosti. U toj aritmetici, (sa najbrzim poznatim algoritmima) slozenost racunskih operacija iznosi:
- O(n) za sabiranje i oduzimanje, kao i za mnozenje i delenje malim vrednostima (koje su unutar opsega ugradjenih tipova), npr. sa 2 i za poredjenje (u najgorem slucaju),
- O(n log(n)) za mnozenje,
- O(n log
2(n)) za delenje, kao i za korenovanje proizvoljnog stepena.
Moj algoritam za kodiranje ima dva sabiranja, jedno mnozenje i jedno delenje sa dva, odnosno slozenost O(n log(n)). Moj algoritam za dekodiranje ima O(log(n)) iteracija koje ukljucuju poredjenje, sabiranje, mnozenje i delenje sa 2. Znaci, iteracije imaju slozenost O(n log(n)), ali posto iteracija ima O(log(n)), cela petlja ima slozenost O(n log
2(n)). Nakon toga imam fiksan broj mnozenja, sabiranja, oduzimanja i delenja sa 2, pa je O(n log
2(n)) ukupna slozenost algoritma.
Branimirov algoritam za kodiranje ima slozenost O(n log(n)) jer ukljucuje fiksan broj sabiranja, oduzimanja, delenja sa 2, mnozenja i poredjenja. Algoritam za dekodiranje ima fiksan broj operacija, od kojih je najzahtevnije delenje (za izracunavanje vrednosti s1), pa ima slozenost O(n log
2(n)).
Dakle, ovako posmatrano, slozenost oba algoritma je ista do na konstantan faktor. Medjutim, ako treba izvrsiti veliki broj kodiranja i dekodiranja sa istom vrednoscu n, onda se veliki broj delenja sa uvek istom vrednoscu moze vrsiti sa slozenoscu O(n log(n)) po delenju, pa u tom slucaju (ako program radi uvek sa istom vrednoscu za n, koja se jednom zadajen na ulazu u program), onda je Branimirov algoritam brzi, tj. ima slozenost O(n log(n)).
Sa druge strane, unutar opsega ugradjenih tipova, jeste da se delenje vuce ko mrcina u poredjenju sa drugim operacijama, ali je ipak brze od moje petlje, jer je hardverki implementirano.
Jos jednom, sve cestitke za Branimira.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.