سلام. مطمئن نیستم درست باشه :|
trace می کنیم.
در ابتدا : Dec=0
در حلقه ی اول:
i=0 … j=1 … $l=power(2,i)=2^0=1$
چون j=l هست پس شرط while یه بار درست هست و داخلش اجرا میشه.
درون while :
s=1 … ++dec
s=4 … ++dec
s=7 … ++dec
s=10 … ++dec
.
.
s=n*n … ++dec
در انتهای while : j=j*2=2
چند بار ++dec انجام شده؟ از ۱ تا n به توان ۲ با گام ۳ : $\frac{n^2}{3}$بار تقریبا
------------------------------------------------------------------------------------
i=1 … j=1 … $l=power(2,i)=2^1=2$
شرط while در ابتدا درست هست که j=1 و l=2 شده.
درون while :
s=1 … ++dec
s=4 … ++dec
s=7 … ++dec
s=10 … ++dec
.
.
s=n*n … ++dec
در انتهای while : j=j*2=2.
چند بار ++dec انجام شده؟ از ۱ تا n به توان ۲ با گام ۳ : $\frac{n^2}{3}$بار تقریبا
حالا j=2 شده و l هم که درست هست، پس یه بار دیگه شرط while درست هست و داریم:
درون while :
s=1 … ++dec
s=4 … ++dec
s=7 … ++dec
s=10 … ++dec
.
.
s=n*n … ++dec
در انتهای while : j=j*2=2.
چند بار ++dec انجام شده؟ از ۱ تا n به توان ۲ با گام ۳ : $\frac{n^2}{3}$بار تقریبا
------------------------------------------------------------------------------------
i=2 … j=1 … $l=power(2,i)=2^2=4$
شرط while دفعه ی اول که j=1 هست، دفعه ی دوم که j=2 میشه و دفعه ی سوم که j=4 میشه درست هست چون از l کوچیکتر هست. پس سه بار داخل حلقه ی while اجرا میشه.
------------------------------------------------------------------------------------
i=3 … j=1 … $l=power(2,i)=2^3=8$
شرط while دفعه ی اول که j=1 هست، دفعه ی دوم که j=2 میشه و دفعه ی سوم که j=4 میشه و دفعه ی چهارم که j=8 میشه درست هست چون از l کوچیکتر هست. پس چهار بار داخل حلقه ی while اجرا میشه.
------------------------------------------------------------------------------------
i=4 … j=1 … $l=power(2,i)=2^4=16$
شرط while دفعه ی اول که j=1 هست، دفعه ی دوم که j=2 میشه و دفعه ی سوم که j=4 میشه و دفعه ی چهارم که j=8 میشه و دفعه ی پنجم هم درست هست چون از l کوچیکتر هست. پس پنج بار داخل حلقه ی while اجرا میشه.
خب پس به ازای هر i اون حلقه ی while به اندازه ی $\log l\: +1$ بار انجام میشه و هر بار هم هزینه ش میشه $\theta(n^2)$
$l=2^i$
$\sum^{n-1}_{i=1}\log2^i+1$ بار حلقه ی while اجرا میشه که هر بار هزینه ش $\theta(n^2)$ هست.
پس کل هزینه و مقدار نهایی dec میشه : $n^2\times\sum^{n-1}_{i=1}\log2^i+1=n^2\times\sum_{i=1}^{n-1}i+1=n^2\times[2+3+...+n]=\theta(n^4)$