zależności między dużym O a dużym Theta

Question

Cześć, mam takie zadanie na studiach do zrobienia i czytam już od 2 godzin o tych notacjach duże O i Theta i nie rozumiem jakie są związki między tymi dwiema notacjami więc prosiłbym kogoś o wytłumaczenie mi łopatologicznie jak wyglądają związki między nimi.Dodatkowo mam ocenić poprawność tych równań i nie wiem jak to sie ma do tego co czytam :( Help pls.

 

n^2 = Θ(n)

n^2 = Θ(n2 )

Jeśli f(n)=O(n 2 )) to f(n)=O(n 3 ).

Jeśli f(n)=O(g) to f(n)=Θ(g).

Jeśli f(n)=Θ(g) to f(n)=O(g).

Jeśli f(n)=O(g) to g(n)=O(f).

Answer 1

Notacja O jest ograniczeniem asymptotycznym 'z góry', np. masz funkcję y = x^2 i musisz określić, czy y = O(x^3). czyli musisz sprawdzić, czy funkcja y = c * x^3 jest większa dla każdej wartości x powyżej pewnego progu x0 (c jest stałą większą od 0). Wiem, że brzmi to skomplikowanie, ale zasadniczo sprowadza się do rozwiązania nierówności:

c * x^3 >= x^2 <=> c * x^3 - x^2 >= 0 <=> x^2(cx - 1) >= 0 <=> cx - 1 >= 0 => cx >= 1

Ponieważ notacje O, Ω  i Θ  stosuje się zazwyczaj do danych, czyli liczb naturalnych, to możemy nałożyć to ograniczenie i uzyskamy:

cx >= 1 i x N => c >= 1

Czyli dla każdej ilości danych x^3 > x^2, co oznacza, że x^3 ogranicza z góry x^2, więc x^2   O(x^3)

Notacja Ω jest przeciwieństwem notacji O, czyli ogranicza 'od dołu', np. funkcja y = x będzie ograniczała od dołu funkcję y = x^2 (tak samo jak poprzednio - rozwiązujemy nierówność: c*x <= x^2 ...). Jeśli da się ograniczyć funkcję z góry i z dołu, za pomocą tej samej klasy funkcji, to stosujemy notację Θ, np. funkcję y = (3/2)x^2 można ograniczyć z góry za pomocą funkcji y = 2x^2 i od doły za pomocą funkcji y = x^2. Zauważ, że mamy tę samą klasę funkcji - x^2, różnią się one tylko stałymi współczynnikami: c1 = 1, c2 = 2, te współczynniki wynikają z rozwiązania podwójnej nierówności:

c1 * x^2 <= (3/2)x^2 <= c2 * x^2

Zatem (3/2)x^2  Θ(x^2)