Asymptotyczne tempo wzrostu – miara określająca zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.
Do opisu asymptotycznego tempa wzrostu stosuje się notację dużego (omikron; U+039F, kod HTML: Ο, Math: \Omicron) oraz jego modyfikacje, m.in. notacja (omega), (theta).
Notacja dużego została zaproponowana po raz pierwszy w roku 1894 przez niemieckiego matematyka . W późniejszych latach spopularyzował ją w swoich pracach Edmund Landau, niemiecki matematyk, stąd czasem nazywana jest notacją Landaua.
Definicje analityczne Niech będą dane funkcje oraz których dziedziną jest zbiór liczb naturalnych, natomiast przeciwdziedziną zbiór liczb rzeczywistych dodatnich.
Notacja „duże Ο” Mówimy, że jest co najwyżej rzędu gdy istnieją takie stałe oraz że:
Zapis:
Określenia „złożoność co najwyżej ” i „złożoność ” są matematycznie równoważne.
Wersja notacji dla zachowania się funkcji w pobliżu punktu
jeżeli istnieje takie i takie że dla każdego o tej własności, że zachodzi nierówność: