(۰۹ مهر ۱۳۹۳ ۱۲:۳۸ ب.ظ)miladcr7 نوشته شده توسط:  سلام فرض کن تابع ما این شکلی باشه:

$g(n)=\{^{n\rightarrow n\: is\: even}_{1\rightarrow n\: is\: odd}$

خب میبینی به ازای $n$ های زوج مقدار تابع $n$ و به ازای $n$ های فرد مقدار تابع $1$ میشه

خب حالا دقت کن که ماکزیمم مقدار تابع $n$ هستش پس:
$g(n)\in O(n)$

ولی چون مقدار تابع بین $1$ و $n$ متغیره پس داریم:
$g(n)\notin Ω(n)$

پس حالا داریم که :
$g(n)\in O(n)-Ω(n)$

خب از طرفی هم معلومه که این تابع عضو $o(n)$ نیستش چون توابعی عضو $o(n)$ هستند که رشدشون کمتر از $o(n)$ باشه ولی رشد این تابع به ازای $n$های زوج برابر $o(n)$ میشه که قابل قبول نیست

در نهایت:
$O(n)-Ω(n)\ne o(n)$