הוכחת "O של"

[chendoy]

הוכחת "O של"

שלום,

מבקש עזרה בהוכחה פורמלית של העובדות בתמונה במצ"ב.

תודה

 

[אורי769]

הדרכה

צריך להתחיל מהגדרה
((f = O(g(n
אם קיימים K ו-N שלכל n>N מתקיים (f <= K*g(n

הסעיף הראשון הוא כמעט טריויאלי. נשים לב שלכל n מתקיים n^n <= n!^n
לכן עבור K=1 ו-N=1 התנאי מתקיים.

בשני הסעיפים האחרים אפשר להוכיח באינדוקציה שאם הביטוי משמאל קטן מהביטוי מימין עבור n אז זה גם כך עבור n+1. זה מצריך קצת עבודה אלגברית.

 

[chendoy]

תודה