حل تشریحی سوال شماره 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)$ صرف کند.