נסמן את זמן הריצה של Alg(A, i, j) כ
T
(
i
,
j
)
{\displaystyle \displaystyle T(i,j)}
נצייר את
עץ הפרישה של הפונקציה:
עץ הפרישה. ט"ו בשבט שמח. מהפרישה אפשר לראות (ולהוכיח פורמלית באינדוקציה), שכל רמה תורמת
Θ
(
n
)
{\displaystyle \displaystyle \Theta (n)}
h
{\displaystyle \displaystyle h}
Θ
(
h
⋅
n
)
{\displaystyle \displaystyle \Theta (h\cdot n)}
h
{\displaystyle \displaystyle h}
נפתור
n
1
2
h
=
k
{\displaystyle \displaystyle n^{\frac {1}{2^{h}}}=k}
log
(
n
)
2
h
=
log
(
k
)
⇒
2
h
=
log
(
n
)
log
(
k
)
⇒
h
=
Θ
(
log
log
(
n
)
)
{\displaystyle \displaystyle {\frac {\log(n)}{2^{h}}}=\log(k)\Rightarrow 2^{h}={\frac {\log(n)}{\log(k)}}\Rightarrow h=\Theta (\log \log(n))}
Θ
(
n
⋅
log
log
(
n
)
)
{\displaystyle \displaystyle \Theta (n\cdot \log \log(n))}
