הדרכה
צריך להתחיל מהגדרה
((f
= O(g(n
אם קיימים K ו-N שלכל n>N מתקיים (f
<= K*g(n
הסעיף הראשון הוא כמעט טריויאלי. נשים לב שלכל n מתקיים n^n <= n!^n
לכן עבור K=1 ו-N=1 התנאי מתקיים.
בשני הסעיפים האחרים אפשר להוכיח באינדוקציה שאם הביטוי משמאל קטן מהביטוי מימין עבור n אז זה גם כך עבור n+1. זה מצריך קצת עבודה אלגברית.