حل تشریحی سوال شماره 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(\text{f(n)}\right)$ است.

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