سلام.
توی این جا میبینیم که بالاخره توی اونی که قرمز کردم متغیر اول میرسه به ۱یعنی n/2^x میشه یک منتهی هنوز k همون k هست و تغییر نکرده.
از اون به بعد رو با سبز نشون دادم که چه اتفاقی میفته.
خب ارتفاع تا جایی که قرمز رنگ هست میشه log در پایه ی ۲ اما این ارتفاع درخت نیست و درخت همچنان ادامه داره تا k هم به یک برسه. با نارنجی نشون دادم.
ارتفاع از سبز تا نارنجی هم میشه log در پایه ی ۴. پس ارتفاع درخت میشه جمع این دو تا
اگه از شاخه ی راست حساب کنیم هم به همین نتیجه میرسیم.

---

کلا وقتی که درخت بازگشت بر حسب بیش از یک متغیر هست باید تغییر همه ی متغیر ها و رسیدن همه شون به شرایط اولیه رو در نظر بگیریم.
مثلا واسه مثال $T(n)=T(\frac{n}{2})+T(\frac{n}{4})$ رو در نظر بگیرید. شاخه ی سمت راست داره هر بار به ۴ تقسیم میشه تا برسه به $T(1)$ یعنی ارتفاعش میشه $\log_4n$ و شاخه ی سمت چپ هر بار داره به ۲ تقسیم میشه تا برسه به شرط اولیه که $T(1)$ باشه. توی سوالای دیگه ممکنه چیز دیگه باشه. یعنی ارتفاعش میشه $\log_2n$
اما در مورد شاخه های وسطی. هر گره توی شاخه های وسطی یا هر بار داره به ۲ تقسیم میشه یا گاهی به ۴. حداقل یه بار به ۴ تقسیم شده پس ارتفاعش از $\log_2n$ قطعا کمتر هست. حداقل یه بار هم به ۲ تقسیم شده پس ارتفاعش از $\log_4n$ بیشتر هست. یعنی ارتفاعش یه چیزی بین ارتفاع شاخه ی راست و چپش هست.