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

واسه به دست آوردن مجموع هزینه های سطوح
با توجه به بالا که :
هزینه به ازای $T(n)$ برابر هست با $\frac{n}{\log n}$
هزینه برای $T(\frac{n}{2})$ برابر میشه با $\frac{\frac{n}{2}}{\log(\frac{n}{2})}=\frac{\frac{n}{2}}{\log n-\log_22}=\frac{\frac{n}{2}}{\log n-1}$
هزینه برای $T(\frac{n}{4})$ برابر میشه با $\frac{(\frac{n}{4})}{\log(\frac{n}{4})}=\frac{\frac{n}{4}}{\log n-\log4}=\frac{\frac{n}{4}}{\log n-1}$
هزینه به ازای $T(\frac{n}{2^k})$ برابر میشه با $\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}$
جمع هزینه ی سطح دوم میشه: $2.\frac{\frac{n}{2}}{\log(\frac{n}{2})}$
جمع هزینه ی سطح سوم میشه: $۴.\frac{\frac{n}{۴}}{\log(\frac{n}{۴})}$
.
.
جمع هزینه ی سطح kام میشه: $۲^k.\frac{\frac{n}{2^k}}{\log(\frac{n}{2^k})}$
جمع هزینه های کل سطوح:
$\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}+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}$
چون $2^k=n\:$ هست جمع آخرین سطح به اون صورت شد. از طرفی مخرج نمیتونه ۰ باشه.
$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$