Algorytmy i Struktury danych

Question

Czy można ograniczyć duże O (ograniczenie górne) Omegą (ograniczenie dolne) inną niż Omega(1)? Pytałam się dwóch ćwiczeniowców i jeden mówi ze odpowiedz błędna a drugi że wszystko się zgadza. (Chodzi o pierwsza odpowiedz z Omegą) lepsza jakość - Screen zadania: https://imgur.com/a/ssboyXh
Skoro we wszystkich sytuacjach nasze W posiada górne ograniczenie W(Alg, n) = O (...) to wydawało mi się że jedyne czym możemy ograniczyć duże O z dołu jest Ω(1).

Answer 1

Czym jest Omega (1)? Funkcja liniową - stałą o wartości jeden,  ona nie ogranicza funkcji rosnącej więc ogranicza tylko funkcje które nigdy nie będą większe niż 1.
Niestety nie ma ograniczenia dolnego ponieważ dla wartości ułamkowych funkcja jest 1/limes -> nieskończoności bo bo choćby 1/2 jest już mniejsze niż 1.
natomiast 1/nieskończoność zbliża się do 0. stąd granica dolna to 0

Comments

Wydaje mi się że algorytm nie może mieć dolnego ograniczenia 0, bo wykona się co najmniej raz więc złożoność (nieważne czy w sytuacji Average czy Worst) nie może wynosić mniej niż 1.

---

ale nie mówie, że ma ... granica to 0, nie ograniczenie... algorytm nigdy nie osiągnie 0, ale zmierza bo 1/ n -> do nieskończoności ma granice 0