Twierdzenie o rekursji uniwersalnej

[Sakurzasty]

Witam,

proszę o pomoc z rozwiązaniem zadania. Muszę dokonać oszacowania dla następującej funkcji

\(\displaystyle{ T \left( n \right) =25T \left( \frac{n}{5} \right) +7n^{3} - 2n^{2} + 3 }\)

Z powyższego wyliczyłem:
\(\displaystyle{ a= 25, b=5, f\left( n\right)=7n^{3} - 2n^{2} + 3 }\)
\(\displaystyle{ x = \log _{b}{a} = \log _{5}{25} = 2 }\)
\(\displaystyle{ n ^{x} = n ^{2} }\)
\(\displaystyle{ \Theta \left( f\left( n\right) \right) = \Theta \left( 7n^{3} - 2n^{2} + 3\right) = \Theta \left(n^{3} \right) }\)
\(\displaystyle{ f\left( n\right) = \Omega\left( n ^{x + \epsilon} \right) = \Omega\left( n ^{2+ \epsilon} \right) }\) dla np. \(\displaystyle{ \epsilon = 0,5 }\)

Natomiast mam problem z udowodnieniem, że istnieje takie c mniejsze od 1 i dostatecznie dużych n, że zachodzi warunek
\(\displaystyle{ af\left( \frac{n}{b} \right) \le cf\left( n\right) }\)

Gdyż
\(\displaystyle{ 25f\left( \frac{n}{5} \right) = 25 \cdot 7 \cdot \left( \frac{n}{5} \right)^{3} - 25 \cdot 2 \cdot \left( \frac{n}{5} \right)^{2} + 3 }\)
i wtedy wychodzi że \(\displaystyle{ 1,4 n^{3} }\), co jednoznacznie wskazuje że nie istnieje takie C, które spełniałoby ten warunek.

Czy gdzieś popełniłem błąd w obliczeniach? Będę niezwykle wdzięczny za pomoc

[arek1357]

viewtopic.php?f=13&t=437954&p=5568626#p5568626

[Sakurzasty]

O tym wiem, ale niestety mogę stosować wyłącznie przedstawioną metodę do rozwiązań tego zadania.
Taki wymóg od wykładowcy i nie jestem w stanie tego przeskoczyć

[arek1357]

Czas najwyższy zmienić wykładowcę

[Dasio11]

\(\displaystyle{ 25f\left( \frac{n}{5} \right) = 25 \cdot 7 \cdot \left( \frac{n}{5} \right)^{3} - 25 \cdot 2 \cdot \left( \frac{n}{5} \right)^{2} + 3 }\)
i wtedy wychodzi że \(\displaystyle{ 1,4 n^{3} }\), co jednoznacznie wskazuje że nie istnieje takie C, które spełniałoby ten warunek.

W jaki sposób tak Ci wychodzi?

Zauważ, że

\(\displaystyle{ \lim_{n \to \infty} \frac{25 f \left( \frac{n}{5} \right)}{f(n)} = \lim_{n \to \infty} \frac{ \frac{7}{5} n^3 - 2n^2 + 75}{7n^3 - 2n^2 + 3} = \frac{1}{5}}\),

więc dla dostatecznie dużych \(\displaystyle{ n}\) powyższy iloraz jest mniejszy od \(\displaystyle{ \frac{1}{2}}\), czyli \(\displaystyle{ 25 f \left( \frac{n}{5} \right) \le \frac{1}{2} f(n)}\).