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

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

$T(n)=({\sqrt {k}})T({\sqrt {k}})+O(n)$

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