حل تشریحی سوال شماره 11 ساختمان داده ها و طراحی الگوریتم ها

کدام یک از گزاره‌های زیر درست است؟

الف- اینکه زمان حل یک مسئله P حد پایین $\Omega \left(n^2\right)$ دارد به این معنی است که برای هر الگوریتم A که P را حل می‌کند فقط برخی از نمونه‌های P وقتی به‌عنوان ورودی به A داده شوند، باعث می‌شود A زمان $\Omega \left(n^2\right)$ صرف کند.

ب- اینکه زمان حل یک مسئله P حد پایین $\Omega \left(n^2\right)$ دارد به این معنی است که برای هر الگوریتم A که P را حل می‌کند هر نمونه از P که به‌عنوان ورودی به A داده شود، باعث می‌شود A زمان $\Omega \left(n^2\right)$ صرف کند.