Mam do wykazania dokładne asymptotyczne oszacowanie na rekurencje
T(n) = T(n-sqrt(n)) + 1
Odpowiedz to T(n) = Theta(sqrt(n)).
Przyjszyjmy się najpierw ograniczeniu górnemu, jeżeli pokażę, że operacja n -> n-sqrt(n) po O(sqrt(n)) krokach zmniejsza n o co najmniej n/2, to wystarczy zeby wykazac ze laczny czas jest O(sqrt(n)) (przesumowanie sumy), jednak nie wiem jak dokonać tego kroku, jakieś pomysły?