با درود
دوستان اینجا چرا ۲ به توان لگاریتم n شده؟ چرا به توان؟
چون اگر من به جای ۲ به ۴ برسم. میشه ۴ به توان لگاریتم n
![[تصویر: 402437_1a5b_tree.jpg]](https://img.manesht.ir/402437_1a5b_tree.jpg)
اون [tex]2^{\log\: n}[/tex] تعداد گره های درخت در سطح آخر است .
دقت کنید تعداد گره ها در سطح صفرم (ریشه) برابر [tex]2^0[/tex] در سطح اول برابر [tex]2^1[/tex] و ... است
درخت [tex]\log\: n[/tex] تا سطح دارد و تعداد برگ ها [tex]2^{\log n}[/tex] است که هر کدام از نودهای درخت پیچیدگی برابر [tex]T(1)[/tex] دارند پس پیچیدگی در سطح آخر برابر است با [tex]T(1)\times2^{\log n}=n[/tex]
پس پیچیدگی سطح آخر هم مانند تمام سطح ها برابر n است
کلا [tex]\log n[/tex] تا سطح داریم پس پیچیدگی کل درخت برابر است با nlogn