سلام.
ریشه ی درخت یعنی هزینه به ازای [tex]T(n)[/tex] برابر هست با [tex]\frac{n}{\log n}[/tex]
پس هزینه برای [tex]T(\frac{n}{2})[/tex] برابر میشه با [tex]\frac{\frac{n}{2}}{\log(\frac{n}{2})}=\frac{\frac{n}{2}}{\log n-\log_22}=\frac{\frac{n}{2}}{\log n-1}[/tex]
هزینه به ازای [tex]T(\frac{n}{2^k})[/tex] برابر میشه با [tex]\frac{\frac{n}{2^K}}{\log(\frac{n}{2^K})}=\frac{\frac{n}{2^k}}{\log n-\log_22^K}=\frac{\frac{n}{2^k}}{\log n-k}[/tex]
کی میرسیم به ریشه ی درخت؟ وقتی به شرط های اولیه برسیم. اغلب [tex]T(۱)[/tex] یا [tex]T(۲)[/tex]
باید ببینیم این روال تقسیم n به ۲ کجا میرسه به ۲ یعنی [tex]T(\frac{n}{2^k})[/tex] کی برابر با [tex]T(2)[/tex] میشه؟
[tex]T(\frac{n}{2^k})=T(2)\: \: \longrightarrow\: (\frac{n}{2^k})=2\: \: \longrightarrow\: n=2^{k\: }\: \: \: \longrightarrow k=\log n-1[/tex]
چرا ۲؟ چون مخرج نباید ۰ باشه. اگه ۱ در نظر بگیریم مخرج ۰ میشه.
اینم یه مثال دیگه از محاسبه ی ارتفاع درخت :https://manesht.ir/forum/thread-33826.html

واسه به دست آوردن مجموع هزینه های سطوح
با توجه به بالا که :
هزینه به ازای [tex]T(n)[/tex] برابر هست با [tex]\frac{n}{\log n}[/tex]
هزینه برای [tex]T(\frac{n}{2})[/tex] برابر میشه با [tex]\frac{\frac{n}{2}}{\log(\frac{n}{2})}=\frac{\frac{n}{2}}{\log n-\log_22}=\frac{\frac{n}{2}}{\log n-1}[/tex]
هزینه برای [tex]T(\frac{n}{4})[/tex] برابر میشه با [tex]\frac{(\frac{n}{4})}{\log(\frac{n}{4})}=\frac{\frac{n}{4}}{\log n-\log4}=\frac{\frac{n}{4}}{\log n-1}[/tex]
هزینه به ازای [tex]T(\frac{n}{2^k})[/tex] برابر میشه با [tex]\frac{\frac{n}{2^K}}{\log(\frac{n}{2^K})}=\frac{\frac{n}{2^k}}{\log n-\log_22^K}=\frac{\frac{n}{2^k}}{\log n-k}[/tex]
جمع هزینه ی سطح دوم میشه: [tex]2.\frac{\frac{n}{2}}{\log(\frac{n}{2})}[/tex]
جمع هزینه ی سطح سوم میشه: [tex]۴.\frac{\frac{n}{۴}}{\log(\frac{n}{۴})}[/tex]
.
.
جمع هزینه ی سطح kام میشه: [tex]۲^k.\frac{\frac{n}{2^k}}{\log(\frac{n}{2^k})}[/tex]
جمع هزینه های کل سطوح:
[tex]\frac{n}{\log n}+2.\frac{\frac{n}{2}}{\log(\frac{n}{2})}+4.\frac{\frac{n}{4}}{\log(\frac{n}{4}​)}+...+2^k\frac{\frac{n}{2^k}}{\log(\frac{n}{2^k})}[/tex]
[tex]\frac{n}{\log n}+2.\frac{\frac{n}{2}}{\log(\frac{n}{2})}+4.\frac{\frac{n}{4}}{\log(\frac{n}{4}​)}+...+2^k\frac{\frac{n}{2^k}}{\log(\frac{n}{2^k})}=\frac{n}{\log n}+\frac{n}{\log n-1}+\frac{n}{\log n-2}+...+\frac{n}{\log2}[/tex]
چون [tex]2^k=n\: [/tex] هست جمع آخرین سطح به اون صورت شد. از طرفی مخرج نمیتونه ۰ باشه.
[tex]n\cdot(\frac{1}{\log n}+\frac{1}{\log n-1}+...+\frac{1}{1})=n.\sum^{\log n}_{i=1}\frac{1}{i}=n.\ln\log n[/tex]