نماد O بزرگ

فرض کنید (f (x) ,g (x توابعی باشند که روی زیرمجموعه‌ای از اعداد حقیقی تعریف شده باشند آنگاه داریم:

اگر و تنها اگر عدد حقیقی مثبت M و عدد حقیقی x ₀ موجود باشد به طوری که:

این علامت برای توصیف رفتار تابع نزدیک یک عدد حقیقی مانند a (معمولاً، a = 0) نیز به کار می‌رود:

اگر و تنها اگر عدد مثبتی مانند δ و M موجود باشند به طوری که:

اگر زمان، (T(n، لازم برای حل مسئله‌ای با n ورودی برابر باشد با:

${\displaystyle T(n)=4n^{2}-5n+7}$

آنگاه اگر تعداد ورودی این مسئله به بی‌نهایت میل کند اندازه جمله ${\displaystyle n^{2}}$ بسیار بزرگتر از دیگر جمله‌ها خواهد بود. در این صورت گفته می‌شود:

${\displaystyle T(n)\in O(n^{2})}$

و یا:

${\displaystyle T(n)=O(n^{2})}$

این بدان معنی است که اگر تعداد ورودی ۲ برابر شود زمان حل (با فرض زیاد بودن تعداد ورودی) ۴ برابر خواهد شد.

در استفاده معمولی تعریف دقیق و رسمی علامت O مورد استفاده قرار نمی‌گیرد بلکه علامت O بزرگ برای تابع (f (x به صورت زیر ساده می‌شود:

• اگر (f (xمجموع توابع مختلف باشد، تابع با سرعت رشد بیشتر را نگه داشته و بقیه را حذف می‌کنیم.
• اگر (f (xمضربی از چند فاکتور مختلف باشد هر مقدار ثابتی را حذف می‌کنیم.

به عنوان مثال فرض کنید

و ما می‌خواهیم این تابع را با استفاده از علامت O بزرگ ساده کنیم، این تابع مجموع سه تابع 6x⁴, −2x³، و 5 است. تابع با نرخ رشد سریع تر همان تابع از مرتبه بیشتر است یعنی: 6x⁴. حال قانون دوم را اجرا می‌کنبم:

6x⁴ ضرب 6 و x⁴ است که اولی به x وابسته نیست بنابراین آن را حذف می‌کنیم و تنها x⁴ می‌ماند در نتیجه: (f (x) = O (x⁴

علامت O بزرگ دو دامنه کاربرد دارد:

• در ریاضیات معمولاً برای نشان دادن این که یک سری هندسی متناهی تا چه اندازه به تابع مورد نظر نزدیک است، خصوصاً در مورد سری تیلور ناقص از این علامت استفاده می‌شود.
• در علوم کامپیوتر این علامت در تحلیل الگوریتم‌ها کاربرد دارد.

در هر دو کاربرد تابع (g (xکه در O(...) به گونه‌ای انتخاب می‌شود که تا حد امکان ساده باشد.

علامت O بزرگ اولین بار توسط متخصص اعداد Paul Bachmann در سال ۱۸۹۴، در جلد دوم کتاب Analytische Zahlentheorie معرفی شد (که جلد اولش در سال ۱۸۹۲ چاپ شده و شامل این علامت نبود). این علامت در کارهای نظریه اعداد توسط ادموند لانداو متداول شد و به همین خاطر گاهی از آن به نام Landau symbol یاد می‌شود.

این علامت در علوم کامپیوتر توسط دانلد کنوت (که علامت‌های مربوطه امگا و تتا را نیز برای اولین بار معرفی کرد) مشهور شد. او هم چنین متذکر شد که علامت امگا توسط Hardy و Littlewood تحت معنی اندکی متفاوت قبلاً تعریف شده بوده‌است.