ignoruje stałe zależne od komputera (dzięki temu analiza jest uniwersalna, uzyskujemy te same wyniki niezależnie od maszyny), zwraca uwagę na wzrost funkcji
Notacja O (górna granica) istnieją stałe takie, że dla wszystkich
Przykład:
Zwróć uwagę, że to funkcje, nie wartości. Ponadto równość jest „w jedną stronę”!
(Dokładniej operując na zbiorach powinno się pisać więc, np. jest zbiorem funkcji i we wzorach traktuje się ten zbiór jako anonimową funkcję )
Notacja (ograniczenie dolne) istnieją stałe takie, że dla wszystkich
Przykład: gdzie
Notacja (tight bounds) istnieją dodatnie stałe takie, że dla wszystkich
lub inaczej:
Przykład:
Notacja o (małe O) Notacje O i są jak i Notacje o i sa jak i
dla każdej dodatniej stałej istnieje stała taka, że dla wszystkich
Przykład: i
Notacja (patrz: Notacja o)
dla każdej dodatniej stałej istnieje stała taka, że dla wszystkich
Przykład: gdzie
Zobacz też teoria obliczeń złożoność obliczeniowa
Kategoria:Algorytmika