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

[tex]g(n)=\{^{n\rightarrow n\: is\: even}_{1\rightarrow n\: is\: odd}[/tex]

خب میبینی به ازای [tex]n[/tex] های زوج مقدار تابع [tex]n[/tex] و به ازای [tex]n[/tex] های فرد مقدار تابع [tex]1[/tex] میشه

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

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

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

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

در نهایت:
[tex]O(n)-Ω(n)\ne o(n)[/tex]