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

---

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