Notacja asymptotyczna

[posoni]

Witam,
czy ktoś mógłby mi pomóc w rozwiązaniu zadania:
Pokaż, że dla dowolnych rzeczywistych stałych \(\displaystyle{ a, b \in R_+}\) zachodzi \(\displaystyle{ (n+a)^b = \Theta(n^b)}\).

[Crizz]

\(\displaystyle{ (n+a)^b = \Theta(n^b)}\)

Nierówność \(\displaystyle{ (n+a)^{b} \le cn^{b}}\) jest równoważna nierównościom:
\(\displaystyle{ \frac{(n+a)^{b}}{n^{b}} \le c}\)
\(\displaystyle{ \left(\frac{n+a}{n}\right)^{b} \le c}\)
\(\displaystyle{ 1+\frac{a}{n} \le \sqrt{c}}\)
Wystarczy zatem, że \(\displaystyle{ \sqrt{c}=1+a}\), czyli \(\displaystyle{ c=(1+a)^{b}}\). Stąd \(\displaystyle{ (n+a)^{b}=O(n^{b})}\)

Nierówność \(\displaystyle{ (n+a)^{b} \ge cn^{b}}\) jest równoważna nierównościom:
\(\displaystyle{ \frac{(n+a)^{b}}{n^{b}} \ge c}\)
\(\displaystyle{ \left(\frac{n+a}{n}\right)^{b} \ge c}\)
\(\displaystyle{ 1+\frac{a}{n} \ge \sqrt{c}}\)
Wystarczy zatem, że \(\displaystyle{ \sqrt{c}=1}\), czyli \(\displaystyle{ c=1}\). Stąd \(\displaystyle{ (n+a)^{b}=\Omega(n^{b})}\)

Ostatecznie, skoro \(\displaystyle{ (n+a)^{b}=O(n^{b}) \wedge (n+a)^{b}=\Omega(n^{b})}\), to \(\displaystyle{ (n+a)^{b}=\Theta(n^{b})}\).