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

ข้อย่อย 1

ข้อความนี้ไม่เป็นจริง โดยการการแสดงตัวอย่างขัดแย้งคือ ให้ $f(n)=n^{2},g(n)=n^{3}$

จะได้ว่า $f(n)=O(g(n))$ นั่นคือ $n^{2}=O(n^{3})$ เป็นจริง แต่ จะได้ว่า $g(n)=O(f(n))$ นั่นคือ $n^{3}=O(n^{2})$ ไม่เป็นจริง

ข้อย่อย 2

ข้อความนี้ไม่เป็นจริง จะแสดงตัวอย่างขัดแย้ง คือให้ $f(n)=n,g(n)=n^{2}$

จะได้ว่า $f(n)+g(n)$ คือ $n+n^{2}=O(n^{2})$

ข้อย่อย 4

ข้อความนี้ไม่เป็นจริง จะแสดงตัวอย่างขัดแย้งคือให้ $f(n)=1/n$ จะได้ว่า ${(f(n))}^{2}=1/n^{2}$

ซึ่ง $(1/n)\neq O(1/n^{2})$

ข้อย่อย 5

อ.วัฒนา