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)}\).
Notacja asymptotyczna
Notacja asymptotyczna
Ostatnio zmieniony 22 lut 2010, o 22:21 przez Althorion, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .
-
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
Notacja asymptotyczna
\(\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})}\).
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})}\).