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

เขียน Recurrence ของเวลาการทำงานของอัลกอริทึมนี้ได้ดังนี้

<math>T(n) =  (\sqrt{n})T(\sqrt{n})+ O(n)</math>

ใช้ Tree ในการหา <math> \Theta </math> ของ T(n) ได้ดังนี้

[[ไฟล์:6.JPG]]