حل تشریحی سوال شماره 8 حل مسئله

هر مسئله محاسباتی با اندازه ورودی n را می‌توان با یک الگوریتمی با زمان چندجمله‌ای برحسب n حل کرد.

برای تمام توابع مثبت f(n) ، g(n) و h(n) ، اگر f(n)=O(g(n)) و $f\left(n\right)=\Omega \left(h\left(n\right)\right)$ باشد، آنگاه $g\left(n\right)+h\left(n\right)=\Omega \left(f\left(n\right)\right)$ است.

اگر هر رقم جداگانه در RADIX SORT را با استفاده INSERTION SORT به‌جای COUNTING SORT مرتب کنیم، آنگاه RADIX SORT به‌درستی کار نمی‌کند (یعنی خروجی صحیح را تولید نمی‌کند).