نماد امگا بزرگ

تعریف ریاضی هریک از نمادهای بالا این‌گونه است:

${\displaystyle f(n)=O(g(n))\Leftrightarrow \exists k:\exists n_{0}:\forall n\geq n_{0}:f(n)\leq k.g(n)}$

${\displaystyle f(n)=o(g(n))\Leftrightarrow \forall k:\exists n_{0}:\forall n\geq n_{0}:f(n)\leq k.g(n)}$

${\displaystyle f(n)=\Omega (g(n))\Leftrightarrow \exists k:\exists n_{0}:\forall n\geq n_{0}:f(n)\geq k.g(n)}$

${\displaystyle f(n)=\omega (g(n))\Leftrightarrow \forall k:\exists n_{0}:\forall n\geq n_{0}:f(n)\geq k.g(n)}$

${\displaystyle f(n)=\Theta (g(n))\Leftrightarrow f(n)=\Omega (g(n)),f(n)=O(g(n))}$

چهار تابع زیر را در نظر بگیرید:

${\displaystyle f(n)=1000n^{2}+20n+16}$

${\displaystyle g(n)=2n^{3}+100n^{\tfrac {4}{3}}+56}$

${\displaystyle h(n)=n^{3}-{\frac {1}{2}}n^{2}+{\frac {1}{3}}n}$

${\displaystyle i(n)={\frac {1}{1000}}n^{4}}$

رفتار این چهار تابع را طبق نمودارشان بررسی می‌کنیم. در ابتدا به نظر می‌رسد تابع ${\displaystyle f}$ با توجه به ضریب بزرگتری که دارد مقدارهای بزرگتری نیز داشته باشد که برای ${\displaystyle n\leq 100}$ هم همین‌گونه است.

نمودار این ۴ تابع وقتی ${\displaystyle n\leq 100}$

اما با بزرگ شدن مقدار ${\displaystyle n}$ رفتار تابع‌ها نیز نسبت به هم متفاوت می‌شود. شکل زیر رفتار توابع را وقتی ${\displaystyle n\leq 1000}$ است نشان می‌دهد. ملاحظه می‌شود که تابع ${\displaystyle g}$ به‌تدریج مقدارش از سایر توابع بیشتر می‌شود

با بزرگتر شدن ${\displaystyle n}$ وضعیت به این شکل در می‌آید: به‌تدریج تابع ${\displaystyle i}$ از بقیه توابع بیش‌تر می‌شود.

و برای مقدار بزرگ ${\displaystyle n}$ داریم:

تابع ${\displaystyle i}$ کاملاً بقیه توابع بیش‌تر می‌شود.

همان‌طور که دیده شد چون این تابع از سایر توابع مرتبهٔ بالاتری داشت در نهایت مقدارش از همهٔ آن‌ها بیشتر شد.

طبق تعاریف بالا می‌تواین رابطهٔ این توابع را برحسب نمادگذاری‌های گفته شده بیان کنیم:

${\displaystyle f(n)=O(g(n))}$ یا ${\displaystyle f(n)=o(g(n))}$و ${\displaystyle g(n)=\Omega (f(n))}$ یا ${\displaystyle g(n)=\omega (f(n))}$

${\displaystyle g(n)=\Theta (h(n))}$ زیرا تابع ${\displaystyle g}$ همواره حدودا دوبرابر تابع ${\displaystyle h}$ است و مرتبهٔ یکسانی دارند.

${\displaystyle h(n)=O(i(n))}$ یا${\displaystyle h(n)=o(i(n))}$

• نماد O بزرگ

• ویکی‌پدیای انگلیسی نماد O بزرگ
• نماد o کوچک