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?
Matematyczny formalizm nie jest moją mocną stroną, ale można np. podstawić pod n k2, wtedy masz T(k2) = T(k^2 - k) + 1. Mentalne rozwinięcie tego przypomina mi wzór 1 + 2 + ... n = (n +1) * n / 2. Jakoś z tego formalny dowód już się chyba da stworzyć.
To raczej nie prowadzi do rozwiazania. Jednak znalazłem już ładną metodę.
Próbowałem coś wczoraj wymyślić, ale nie miałem szczególnie weny więc dałem sobie spokój. Tym niemniej:
To raczej nie prowadzi do rozwiazania. Jednak znalazłem już ładną metodę.
Jeśli zadałeś pytanie na forum i znalazłeś samodzielnie rozwiązanie, dobrym zwyczajem jest pochwalenie się nim.
Tak, tym razem nikt na forum się nie popisał wiedzą, ale być może ktoś inny w przyszłości (za rok, dwa) zajrzy tutaj mając taki sam problem - możesz go uratować :>.