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

ข้อย่อย 1

ใช้ master method กรณีที่ 3

จากโจทย์ $a=2,b=2,f(n)=n^{3}$

จะได้ $n^{log_{b}a}=n^{log_{2}2}=n$

จะได้ $a(f((n/b))=2f(n/2)=(1/4)n^{3}\leq n^{3}$ เมื่อ $c=1/4$

ดังนั้นจะได้ว่า $T(n)=\Theta (f(n))=\Theta (n^{3})$

ข้อย่อย 2

อ.วัฒนา

ข้อย่อย 3

อ.วัฒนา

ข้อย่อย 4

อ.วัฒนา

ข้อย่อย 6

อ.วัฒนา

ข้อย่อย 7

อ.วัฒนา