נסמן את זמן הריצה של Alg(A, i, j) כ T ( i , j ) {\displaystyle \displaystyle T(i,j)} .
Alg(A, 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))} .
