إثبات أن وظيفة f (n) تنتمي إلى ثيتا كبيرة (g (n))

Question

إنه تمرين يطلب الإشارة إلى فئة Big-Theta (g (n)) الوظائف تنتمي إلى التأكيد وإثباتها.

في هذه الحالة f (n) = (n^2+1)^10

بحكم التعريف f (n) e big-theta (g (n)) <=> c1*g (n) <f (n) <c2*g (n) ، حيث c1 و c2 هما ثوابتان.

أعلم أنه بالنسبة لهذا F (n) ، فإن Big-Theta هو G (n^20) لكنني لا أعرف من لإثبات ذلك بشكل صحيح. أعتقد أنني بحاجة إلى التلاعب بهذا عدم المساواة ولكني لا أعرف كيف

Answer 1

دالة f (x) هي θ (g (x)) ، IFF:

• F (x) هو o (g (x)) ، و
• G (x) هو o (f (x))

لذا ، بينما يمكنك محاولة إثبات ذلك في عدم مساواة واحدة ، أقترح عليك تقسيمها إلى هذين الجزأين ؛ إثبات ذلك أولاً لبعض n> n₀ f (n) <c₁ g (n) ، ثم أثبت ذلك لبعض n> n₀ ز (ن) <ج₂ و (ن). بمجرد إثبات كلا الجزأين ، بشكل منفصل ، يمكنك العودة إلى تعريف θ لإثبات أن f = θ (g).

Answer 2

أنا لست خبيراً حقًا في هذا ، لكن لا يمكنك إثبات أن f (n) ο ο (n) وأن f (n) e ω (n) ثم يجادلون بأن f (n) e θ (n) بسبب تعريف التقاطع؟