26
Bu yerda m = n+1, a
1
= n+1, a
m
= 1 va yigʻindisi (n
2
+3n-2)/2.
5-operatorning bahosi xuddi shu tarzda olinadi, shunchaki
unutmang for siklining asosiy qismi har doim tanasiga qaraganda yana
bir marta bajariladi. Bu yerda
.
6- va 7-operatorlarning baholariga kelsak, biz bunga oldinroq duch
kelganmiz.
Kiritilgan ma‘lumotlarga qarab, ushbu operatorlar boshqacha marta
bajarilishi mumkin. "Yaxshi" ma‘lumotlar uchun (massiv allaqachon
saralangan boʻlsa), bu operatorlar hech qachon bajarilmaydi. "Yomon"
ma‘lumotlar uchun ushbu operatorlar har bir tekshirishda min>a[j]
bajariladi. Algoritmlarni saralash uchun "yomon" ma‘lumotlar teskari
tartibda saralangan massivdir.
Shunday qilib, saralash algoritmi uchun eng yaxshi ball n
2
+ 8n-5,
eng yomon koʻrsatkich esa 2n
2
+11n-5. Yomonmi yoki yaxshimi?
Hozircha faqat massiv allaqachon saralangan boʻlsa, algoritm koʻp vaqt
sarflashini sezishingiz mumkin. Bu ushbu algoritmning aniq
kamchiliklaridir.
