Ustal rząd wielkości i zanotuj to za pomocą notacji „duże theta”:

[KasztanWeselny]

Hej, mam zadanie tego typu jak w tytule tematu. i mam problem z jednym z przykładów.

\(\displaystyle{ \log _{5} 3 ^{n} = \Theta(X)}\)

nie bardzo wiem co napisać w miejsce \(\displaystyle{ X}\), powyżej.

[Janusz Tracz]

Zacznijmy od definicji \(\displaystyle{ \Theta \left( X \right) }\). Jakiej kolega używa?

Wskazówka: \(\displaystyle{ \frac{1}{100} n \le \lg_53^n \le 100n }\)

[KasztanWeselny]

X użyłem jako place holder,
Chodzi mi o odpowiedz jak np:

\(\displaystyle{
3 ^{n} + n ^{2} = Θ(3 ^{n})
}\)

Do wyzaczania dokładnego rzędu funkcji będącej sumą wystarczy skupić się na dominującym składniku tej sumy. Nie widzę co jest dominującym składnikiem przykładu z pierwszego postu. Jeśli musiałbym odpowiedzieć to odpowiedziałbym \(\displaystyle{ 3 ^{n}}\), ale jestem niemal pewny, że jest to odpowiedz błędna.

[Janusz Tracz]

Nie o to pytałem. Mówiąc o definicji \(\displaystyle{ \Theta }\) miałem na myśli: co rozumiesz przez zapis: \(\displaystyle{ \alpha _n \in \Theta\left( \xi_n\right) }\), czy jak wolisz \(\displaystyle{ \alpha _n = \Theta\left( \xi_n\right) }\) (choć ten pierwszy jest formalnie poprawny, ten drugi jest powszechnie stosowany). Zatem czy:

\(\displaystyle{ \alpha _n \in \Theta\left( \xi_n\right) \Leftrightarrow \left( \exists N\in\NN , c_1,c_2\in \RR_{>0}\right) \left( \forall n \ge N\right) \ c_1\xi_n \le \alpha_n \le c_2 \xi_n }\)

bo jeśli tak to skorzystaj ze wskazówki którą Ci dałem wystarczy odczytać z niej \(\displaystyle{ \xi_n}\) czyli Twój \(\displaystyle{ X}\). A jeśli:

\(\displaystyle{ \alpha _n \in \Theta\left( \xi_n\right) \Leftrightarrow \lim_{n \to \infty } \left| \frac{ \alpha _n}{\xi_n} \right| \in \left( 0, \infty \right) }\)

co stanowi warunek wystarczający dla pierwszej definicji to policz \(\displaystyle{ \lim_{n \to \infty } \frac{\lg_53^n}{n} }\) i odczytaj \(\displaystyle{ \xi_n}\).