Асимптотическая верхняя граница роста времени/памяти от размера ввода. O(1) - константа; O(n) - линейная; O(n^2) - квадратичная; O(log n) - логарифм; O(n log n) - сортировка. Игнорируем константы и младшие члены.