מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/חסמים עליונים ותחתונים למספר נוסחאות נסיגה/תשובה

 , עפ"י מקרה 1 של משפט המאסטר.

נפרוש את הנוסחה:  
 
 
 
 
 
 
(את המעבר האחרון ראינו בטורים שימושיים.)

נגדיר  . בלי הגבלת הכלליות, נניח ש . להלן עץ הפרישה המתקבל:

 
עץ הפרישה.

בעץ זה, לכל אחד מהצמתים המצויירים שני ילדים: אם הצומת מתאים לגודל  , אז הילד השמאלי מתאים ל ,‏ והימני מתאים ל ,‏. מכאן אפשר לראות שמסלולים שמאליים בעץ קצרים יותר ממסלולים ימניים, כי  .‏ לא כל הרמות בעץ מלאות, אם כן, מה שמקשה מעט על ניתוח הסיבוכיות. נגדיר כ  את אורך המסלול השמאלי ביותר, וכ  את אורך המסלול הימני ביותר.

קל לראות שכל רמה מלאה בעץ תורמת  .‏ הרמה הראשונה תורמת  ;‏ הרמה השניה תורמת  ,‏ הרמה השלישית תורמת  ;‏ וכו'.‏ (אפשר להראות זאת פורמאלית באינדוקציה.)

אפשר לראות, לכן, ש  חסומה מלמטה ע"י  , וחסומה מלמעלה ע"י  . אבל היות ש  וכן  , אז  .