נשתמש בפרישה.בעץ המתאים לנוסחה:
- צומת הראש מציין את
, והרמה הראשונה תורמת
.
- ברמה הבאה, הצומת מציין את
, והרמה תורמת
.
- ברמה הבאה אחריה, הצומת מציין את
, והרמה תורמת
.
החוקיות איננה מסובכת, ונוכל להוכיח את הטענה הבאה באינדוקציה פשוטה: ברמה ה
(כאשר ראש העץ נחשב ברמה ה0), הצומת מציין את
, והרמה תורמת
.
כדי למצוא את גובה העץ,
, נפתור
:
![{\displaystyle \displaystyle n^{1/2^{m}}=2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f422cea4613026f01a42386f6a9a505afee9da7)
![{\displaystyle \displaystyle \log(n^{1/2^{m}})=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3376d744a9c7d80d7b6a75ec262d656e4fcc36bd)
![{\displaystyle \displaystyle 1/2^{m}\cdot \log(n)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6f420ba4d5777af12fb17c31da59ae63c17aa4c)
![{\displaystyle \displaystyle 2^{m}=\log(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5726cdd346debf6ea895feb4c62181738dc2a12f)
![{\displaystyle \displaystyle m=\log(\log(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72e0cbe97ea0fcc02ad039382eda7e53afc742e0)
כאמור, הרמה ה
תורמת
. נותר, לכן, לסכם
את
:
![{\displaystyle \displaystyle \sum _{i=0}^{\log(\log(n))}[1/2^{i}\cdot \log(n)]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93293e0cef32eb10049b63a0ac42739559c7c66f)
![{\displaystyle \displaystyle \sum _{i=0}^{\log(\log(n))}[1/2^{i}]\cdot \log(n)=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ceaef1d9195ba8b0d37daaf0b318d69ef0b830bd)
![{\displaystyle \displaystyle \Theta (1)\cdot \log(n)=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0c6c100c1516046b2c580a9ed8ca8b8d1fda730)
![{\displaystyle \displaystyle \Theta (\log(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df8ab09d45831fdd28a35a70247bcff5fabbf004)