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

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

พิจารณา while ลูป จะได้ว่า while ลูปทำงาน lg i ครั้ง

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

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