Zacznijmy może od notacji O(f(n)) ("duże o"). Jeśli f(n) = O(g(n)) to znaczy, że istnieje pewne n0 od którego funkcja f będzie mniejsza od funkcji g z dokładnością do stałej c, można powiedzieć że będzie ograniczana przez funkcje g z góry, matematycznie wygląda to tak: f(n) < c * g(n), n >= n0. Od pewnego n0 funkcja f będzie zawsze mniejsza niż g. Weźmy przykład z wikipedii:
Tutaj akurat jest na x zamiast n, ale skoro zabrnąłeś tak daleko w matematyke to wiesz, że nie ma różnicy :D. Widzimy, że od pewnego x0 tutaj jakoś 4.5 niebieska funkcja jest większa od czerwonej i to się już nie zmieni aż do nieskończoności. Stała może wynosić 5, 0.000000001 albo nawet 999999999, grunt, że jest to skończona liczba większa od 0. Np n = O(n^2), bo od n0 = 1 i c = 1: c * n^2 będzie zawsze większe od n. Stałe możesz sobie wbrać inne, ważne żeby istniała taka jedna para, dla której równanie jest spełnione: np c = 2 i n0=2.
Notacja z omegą działa tak samo ale obraca zależność. Oznacza, że od pewnego n0 funkcja f będzie większa od funkcji g.
Notacja theta oznacza, że funkcja f od pewnego n0 będzie się mieścić w przedziale c1*g(n) i c2*g(n):
Np 2x = theta(x), bo funkcja f(x) = x zmieści się pomiędzy funkcją x np dla stałych c1 = 0.5 i c2 = 2.
Jeśli dalej masz problemy to możesz zerknąć na tą stronke:
https://pl.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation
Omawia ona te notacje od praktycznej strony, bo wykorzystuje się je bardzo często w opisywaniu złożoności algorytmów.
