Witam!
Zastanawiam się czy jest możliwe żeby jakaś funkcja była jednocześnie małym i dużym O innej.
Np. mamy n + 1
istnieje c = 1 dla którego dla n >= 1 n + 1 < cn2 zatem n2 jest dużym O
ale wydaje mi się, że to zachodzi dla każdego n > 0 (da się znaleźć n od którego n + 1 > cn2) a wtedy n2 jest małym o
Czy to możliwe czy popełniam jakiś błąd?
Z góry dziękuję za pomoc ;)
Pozdrawiam
Na pytanie czy to jest możliwe: jest możliwe, bo O zawiera o.
Ale twój przykład jest zły. Nie istnieje c takie, że istnieje N, że dla każdego n>N n+1>cn^2.
Ale twój przykład jest zły. Nie istnieje c takie, że istnieje N, że dla każdego n>N n+1>cn^2.
ale napisałem odwrotnie
istnieje c takie, że istnieje N, że dla każdego n>N n+1 < cn2 czyli n+1 = O( n2 )
Ale oczywiście dziękuję za odpowiedzi ;)
Takich par funkcji jest bardzo wiele. Dla każdej funkcji f i każdej liczby dodatniej c funkcja cf jest jednocześnie rzędu O(f) i o(f).
Dlaczego?
Przecież jak mam np x i 5x
to owszem 5x = O(x)
ale raczej nie zachodzi 5x = o(x) da się znaleźć stałą np. c = 0.000001 dla której nie będzie spełnione 5x < c * x dla x > od ileśtam