O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini

2- ta’rif. f(n) funksiya Ω(g(n)) deyiladi, agar shunday musbat c va N lar mavjud bo’lsaki , barcha n>=N lar uchun f(n)>=cg(n) tengsizlik o’rinli bo’lsa.

Bu ta’rif ham birinchi ta’rifga juda o’xshash, faqat bu yerda tengsizlik teskaridir.

Yuqoridagi ikkita ta’rifdan foydalanib quyidagio ta’rifni keltirish mumkin.

Ta’rifga asosan f(n) funksiya kamida g(n) funksiya kabi o’sadi. Bu ikkita ta’rif yordamida funksiyalar o’rtasida quyidagi munosabatlar o’rinli bo’lishini aniqlash mumkin:

Ta’rifga asosan f(n) funksiya kamida g(n) funksiya kabi o’sadi. Bu ikkita ta’rif yordamida funksiyalar o’rtasida quyidagi munosabatlar o’rinli bo’lishini aniqlash mumkin: