Asymptotyczne przybliżenie relacji nawrotu (wydaje się, że nie ma zastosowania Akra-Bazzi)

Załóżmy, że algorytm ma relację powtarzalności środowiska wykonawczego:

$T(n) = \left\{ \begin{array}{lr} g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\ f(n) & : n < n_0 \end{array} \right.$

dla niektórych stałych . Załóżmy, że g jest wielomianem w n , być może kwadratowym. Najprawdopodobniej f będzie wykładnicze w n .$0 < \delta < 1$$g$$n$$f$$n$

Jak przejść do analizy środowiska wykonawczego ( byłoby doskonałe)? Wydaje się, że nie można zastosować twierdzenia głównego i bardziej ogólnej metody Akra-Bazzi.$\Theta$

$T'(n) = T(n)-T(n-1)$$T'(n)$$T(n)$

$$T'(n) = T(\lfloor \delta n \rfloor) + g(n).$$ $$t'(x) = t(\delta x) + g(x),$$ $${d \over dx} t(x) = t(\delta x) + g(x).$$

$t(x)$

Zapomniałem wszystkiego, co kiedyś wiedziałem o równaniach różniczkowych, więc nie znam rozwiązania tego równania różniczkowego, ale być może uda się go rozwiązać, przeglądając wszystkie techniki rozwiązywania równań różniczkowych.