418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 5

แต่ละรอบการทำงานของ i

พิจารณา while ลูป จะได้ว่า เมื่อ i มีค่า 1 ลูป while จะไม่ทำงาน เมื่อ i มีค่าเป็น 2 ลูป while จะทำงาน 1 ครั้ง เมื่อ i มีค่าเป็น 3,4 ลูป while จะทำงาน 2 ครั้ง เมื่อ i มีค่าเป็น 5,6,7 ลูป while จะทำงาน 3 ครั้ง ดังนั้นสรุปได้ว่า while ลูปทำงาน lg i ครั้ง และในอัลกอริทึมนี้ i มีค่าตั้งแต่ 1 ถึง n ดังนั้นทั้งอัลกอริทึม ลูป while จะทำงาน lg n ครั้งนั่นเอง

เนื่องจาก ลูป for ทำงานทั้งหมด n ครั้ง (เมื่อ i = 1 ถึง i = n)

ดังนั้น จะได้ว่าเวลาการของอัลกอริทึมนี้โดยเฉลี่ยคือ $\Theta (n(logn))$