تعریف O بزرگ

این فرمول می‌گوید زمان (یا حافظهٔ) الگوریتم با رشد ورودی، حداکثر با چه سرعتی رشد می‌کند.

یعنی از یک n₀ به بعد، $T(n)\le c\cdot f(n)$ برای یک ثابت c. سه پیامدِ عملی: (۱) ثابت‌ها مهم نیستند — $O(2n)$ همان $O(n)$ است؛ (۲) جملهٔ غالب می‌ماند — $O(n^2+n)$ همان $O(n^2)$ است؛ (۳) نماد دربارهٔ «مقیاس» حرف می‌زند نه ثانیه: الگوریتمِ $O(n^2)$ با دوبرابرشدن ورودی تقریباً چهار برابر می‌شود.