نماد O بزرگ: کار با چه سرعتی زیاد می‌شود؟

داستان: دو راه برای پیدا کردن یک نام

روی هر سطر بزن تا کلمه‌هایش را ببینی.

1. $$T_{\mathrm{۱}}(n)=n\Rightarrow T_{\mathrm{۱}}(\mathrm{۱}{\mathrm{۰}}^{\mathrm{۶}})=\mathrm{۱}{\mathrm{۰}}^{\mathrm{۶}}$$راه اول: نام‌ها را یکی‌یکی نگاه کن. در بدترین حالت n بار نگاه؛ برای یک میلیون نام، یک میلیون بار.
2. $$T_{\mathrm{۲}}(n)=\lfloor {\log }_{\mathrm{۲}}n\rfloor +\mathrm{۱}\sim {\log }_{\mathrm{۲}}n$$راه دوم، روی فهرست مرتب: وسط را ببین، نیمهٔ نادرست را دور بینداز، دوباره. حدود log₂ n بار نگاه.
3. $${\mathrm{۲}}^{\mathrm{۱۹}}<\mathrm{۱}{\mathrm{۰}}^{\mathrm{۶}}<{\mathrm{۲}}^{\mathrm{۲۰}}\Rightarrow T_{\mathrm{۲}}(\mathrm{۱}{\mathrm{۰}}^{\mathrm{۶}})=\mathrm{۲۰}$$چون یک میلیون بین ۲ به توان ۱۹ و ۲ به توان ۲۰ است، نصف کردن دقیقاً بعد از ۲۰ بار نگاه تمام می‌شود.
4. $$T_{\mathrm{۱}}(n)=\Theta (n),T_{\mathrm{۲}}(n)=\Theta (\log n)$$یک روش مثل n رشد می‌کند، دیگری مثل log n؛ ضریب ثابت اهمیتی ندارد.
5. $$T_{\mathrm{۲}}(n)=O(T_{\mathrm{۱}}(n)),T_{\mathrm{۱}}(n)=\Omega (T_{\mathrm{۲}}(n))$$جست‌وجوی دودویی، تا یک ضریب ثابت، از جست‌وجوی خطی بیشتر نیست، و جست‌وجوی خطی دست‌کم به اندازهٔ دودویی است.
6. $$T_{\mathrm{۲}}(n)=o(T_{\mathrm{۱}}(n))$$بیشتر از این: نسبت هزینهٔ سریع به هزینهٔ کند به صفر میل می‌کند.
7. $$n<n{\log }_{\mathrm{۲}}n<n^{\mathrm{۲}}<{\mathrm{۲}}^n<n!(n\ge \mathrm{۵})$$وقتی n دست‌کم ۵ باشد، مرتبه‌های رشد بالا می‌روند: n، n log n، n به توان دو، ۲ به توان n، n فاکتوریل.
8. $$\mathrm{۲۰}!\approx ۲٫۴\times \mathrm{۱}{\mathrm{۰}}^{\mathrm{۱۸}}$$امتحان کردن همهٔ ترتیب‌های فقط ۲۰ نام یعنی حدود ۲٫۴ ضرب در ۱۰ به توان ۱۸ ترتیب: نومیدکننده.
9. $$T(n)=\mathrm{۲}T(n/۲)+n$$مرتب‌سازی با تقسیم: دو نیمه را مرتب کن، بعد در n گام ادغامشان کن.
10. $$T(n)=\Theta (n\log n)$$این رابطهٔ بازگشتی به هزینه‌ای از مرتبهٔ n log n حل می‌شود، میان خطی و درجه دو.

این داستان با کلمه‌ها ۸۶۸ حرف است؛ با نمادها ۱۸۷.