سلام.
اول ریشه ی درخت رو میبینیم که هزینه ش چقدر هست. که $n^2$ هست. اون رو به عنوان ریشه میگذاریم.
توی این جا ریشه ۸ تا فرزند $T(\frac{n}{2})$ داره. اون ها رو به عنوان فرزندهاش میگذاریم. توی این سطح هزینه رو حساب میکنیم. هر $T(\frac{n}{2})$ هزینه ش هست $(\frac{n}{2})^2$ پس هزینه ی این سطح میشه ۸ تا $\frac{n^2}{4}$ و در مجموع هزینه ی این سطح میشه $2n^2$
توی سطح بعد هر کدوم از فرزندهای سطح قبل ۸ تا فرزند دارند که هر کدوم $T(\frac{n}{4})$ هستند که کلا ۶۴ تا هستند و هزینه ی هر کدوم میشه $\frac{n^2}{16}$ و در مجموع هزینه ی این سطح میشه $4n^2$
.
.
همونطور که میبینیم هزینه ی سطوح متفاوت هست.
در صورتی که هزینه ی سطح ها با هم برابر باشه هزینه ی کل برابر میشه با ارتفاع درخت ضربدر هزینه ی یک سطح.
اما در اینجا که هزینه ها یکسان نیست و یک تصاعد هندسی رو تشکیل میده هزینه ها رو با هم جمع میکنیم.
$n^2+2n^2+4n^2+8n^2+....+2^kn^2=n^2(2^0+2^1+2^2+....+2^k)$
حالا k ارتفاع درخت هست. چون همون طور که میبینیم توی سطح یک مقدارش برابر با ۱، توی سطح ۲ مقدارش برابر با ۱ و …. هست.
برای به دست آوردن k (ارتفاع درخت):
درخت تا جایی ادامه پیدا میکنه که برسه به برگ ها یعنی $T(1)$ (گاهاََ ممکنه طبق فرضیات $T(1)$ برگ نباشه و $T(2)$ باشه.
حالا باید ببینم که هر سطح از چه قانونی پیروی میکنه و چطور میرسه به برگ.
توی سطح اول داریم: $T(\frac{n}{2^0})$
توی سطح دوم داریم: $T(\frac{n}{2^1})$
توی سطح سوم داریم: $T(\frac{n}{2^۲})$
…
و به همین ترتیب توی سطح k ام داریم : $T(\frac{n}{2^k})$ وقتی که به $T(1)$ برسیم به برگ ها رسیدیم و درخت تا همین جا ادامه پیدا میکنه این k ارتفاع درخت هست.
باید $T(\frac{n}{2^k})==T(1)$ که میشه: $\frac{n}{2^k}=1\: \: \rightarrow\: n=2^{k\: }\rightarrow k=\log n$
پس ارتفاع درخت logn هست. (البته دقیق تر بخوایم بگیم چون تعداد سطوح یکی از ارتفاع بیشتر هست و ما اینجا تعداد سطوح (k) رو به دست آوردیم، ارتفاع درخت $\log n\: -1$ هست.
همونطور که حساب کردیم هزینه ی مجموع سطوح میشد : $n^2\times\sum_{k=0}^{k=\log n}2^k$ و البته طبق توضیح بالا اگه بخوایم دقیق تر بگیم k حداکثر $\log n\: -1$ هست.
خب می دونیم: $2^0+2^1+....+2^{\log n-1}=\Sigma_{k=0}^{\log n-1}2^k=2^0\times\frac{(1-2^{\log n-1+1})}{1-2}=(2^{\log n}-1)=\theta(2^{\log n})=(2^{\log_2^n})=n$
خب پس مرتبه ی تابع (مجموع هزینه های تمام سطوح) میشه:
$n^2\times\: \Sigma_{k=0}^{\log n-1}2^k=n^2\times n=n^3$
$T(n)=\theta(n^3)$