7
Ω –quyi baholashga misollar:
1-misol. f(n) = 5n
2
uchun quyi chegarani toping.
Yechish:
∃ c, n
0
mavjudki: 0 ≤ cn
2
≤ 5n
2
⇒ cn
2
≤ 5n
2
⇒ c = 5 va n
0
=1
∴ 5n2 =
Ω (n
2
) bo’lib, c = 5 va n
0
= 1 ga teng bo’ladi;
2-misol. f(n) = 100n + 5 ≠
Ω (n
2
) ekanligini isbotlang.
Yechish:
∃ c, n
0
mavjudki: 0 ≤ cn
2
≤ 100n + 5
100n + 5 ≤ 100n + 5n(
∀n ≥ 1) = 105n
cn
2
≤ 105n
⇒ n(cn - 105) ≤ 0
n musbat bo'lgani uchun
⇒cn - 105 ≤0 ⇒ n ≤105/c
⇒ Qarama-qarshilik: n konstantadan kichik bo'lishi mumkin emas.
Θ - o’rta baho (o'rtacha asimptotik funktsiya)
Bu baho berilgan funksiya (algoritm) ning yuqori va pastki chegaralari bir xil
yoki yo‘qligini aniqlaydi. Algoritmning o'rtacha ishlash vaqti har doim pastki va
yuqori chegaralar orasida bo'ladi.
Agar yuqori chegara (
