Uzasadnienie odpowiedzi i rozwiązanie

hunter999 · Post autor: **hunter999** » 11 kwie 2016, o 08:54

Niech \(\displaystyle{ t_{n}=\sum_{k-1}^{n} (2k-1)}\) Czy prawdą jest że \(\displaystyle{ t_{n}=0(n^{2})}\). Odpowiedź uzasadnij.

Może mi ktoś pomóc rozwiązać to zadanie bo kompletnie nie wiem od czego zacząć, miałem to na zajęciach ale profesor tego nie wytłumaczył bo miał ważne spotkanie a muszę to zrobić.

janusz47 · Post autor: **janusz47** » 11 kwie 2016, o 11:52

\(\displaystyle{ t_{n}= \sum_{k=1}^{n}(2k-1)= 1+3+5+...+2n-1= \frac{1+2n-1}{2}n= n^{2}.}\)

Jeśli \(\displaystyle{ n \rightarrow \infty}\) to \(\displaystyle{ \frac{t_{n}}{n^{2}} =0}\) i wtedy \(\displaystyle{ t_{n}=o(n^{2}}).}\)

Gdy funkcja \(\displaystyle{ \frac{t_{n}}{n^{2}}}\) jest ograniczona, to \(\displaystyle{ t_{n} = O(n^{2})}\).

Hubbaser · Post autor: **Hubbaser** » 11 kwie 2016, o 11:57

Najpierw wysumuj to to wyrażenie - jest to zwykły ciąg arytmetyczny.
Notacja O (koniecznie wielką literą) oznacza, że te dwa ciągi są asymptotycznie podobne. Czyli, że granica ich ilorazu w nieskończoności jest niezerową liczbą (tu nie jestem pewien czy nie wystarczy ograniczenie przez dwie niezerowe liczby - to musisz doczytać)

@up to nie jest notacja o-małe, tylko O-duże