Złożoność algorytmów

Question

Cześć, mam problem z podaniem funkcji złożoności obliczeniowej do następującego programu :

for(int i=1; i<=n; i++){
 int j=n;
 while(j>=1){
 j= j/2;
 }
}

Mniej więcej wiem jak to robić tylko mam problem z funkcją wew.

Jeśli byłby ktoś wstanie dać jakąś wskazówkę i to wytłumaczyć byłbym wdzięczny :) 

Answer 1

Pętla wewnętrzna wygląda na logarytm przy podstawie 2 z n, czyli razem rząd jest n*log(n)

Answer 2

Śmiesznie, bo jutro mam to do zaliczenia. Najlepiej - imo - podstawiać wartości, pomiędzy czwartą a piątą linią dać coś co zlicza kroki algorytmu. Idąc tym tokiem dostaniemy kolejne wartości, które będą się układać w pewną całość. Łatwo zauważyć, że ilość operacji zwiększa się przy wielokrotnościach dwójki. Może być to zatem funkcja wykładnicza. Ale czy na pewno? Dla n=16 mamy 5 operacji, więc raczej to funkcja odwrotna, czyli logarytm. O jakiej podstawie? Jak wiemy a^x=b wtedy i tylko wtedy gdy log o podstawie a z b=x. Czyli podstawa=2.

Sposób jest toporny, ale nie wiem jak to inaczej ugryźć.