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

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

จะได้ $a=1,b=10/9,f(n)=n$

หา $n^{log_{b}a}=n^{log_{10/9}1=n^{0}=1}$

หา $a(f(n/b))=f(9n/10)=9n/10\leq n$ เมื่อ $c=9/10$

ดังนั้น $T(n)=\Theta (f(n))=\Theta (n)$

ข้อย่อย 3

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

จะได้ $a=16,b=4,f(n)=n^{2}$

หา $n^{log_{b}a}=n^{log_{4}16}=n^{2}$

ดังนั้น $T(n)=\Theta (n^{log_{b}a}\lg n)=\Theta (n^{2}\lg n)$

ข้อย่อย 4

อ.วัฒนา

ข้อย่อย 6

อ.วัฒนา

ข้อย่อย 7

อ.วัฒนา