قبلا به جای تقسیم گذاشته بودید * و من نوشتم دیدم حلقه ی بی نهایت میشه و جواب نداره.
الان که تبدیل به تقسیم کردید دوباره حل کردم.
اول : i=n
تا زمانی که i از ۱ بزرگتر هست، دستورات داخل while اول اجرا میشه.
……………….j=1
……………...تا زمانی که j از n کوچک تر هست، دستورات داخلی while دوم اجرا میشه.
……………………………. j=j*3
………………..……………i=i/2
………………..……………*write
j=1 هر بار در ۳ ضرب میشه تا برسه به n که از شرط while دوم بیرون بیایم. $\log_3n$ بار j در سه ضرب میشه تا برسه به n. دستور چاپ * هم به تعداد $\log_3n$ بار اجرا میشه.
وقتی j به n رسید i چند شده؟ i که قبل از این while دوم n بود الان هر بار با ضربدر ۳ شدن j, تقسیم بر ۲ شده. یعنی$\log_3n$ بار بر ۲ تقسیم شده.
یعنی برای while داخلی:
j=3 ….. i=n/2
$j=3^{2\: }........i=\frac{n}{2^2}$
$j=3^{3\: }........i=\frac{n}{2^3}$
$j=3^{4\: }........i=\frac{n}{2^4}$
.
.
.$j=3^k\: ........i=\frac{n}{2^k}$
تا جایی این ضرب در ۳ برای j ادامه داره که به n برسه. یعنی :
$3^k<=n$
$k=\log_3n$
پس در انتهای حلقه ی while، مقدار i هم شده $\frac{n}{2^k}=\frac{n}{(2^{\log_3n})}=\frac{n}{n^{\log_32}}=\frac{n}{n^{1-t}}$
در این جا $\log_3n$ بار عمل چاپ * انجام شده.
حالا از while دوم مییایم بیرون. شرط while اول برقرار هست، چون i از ۱ بزرگتر هست و دوباره j=1 میشه و به همون ترتیب بالا.
نکته ای که وجود داره این هست که چند بار حلقه ی while دوم انجام میشه؟ و در واقع i تا کی از ۱ بزرگتر خواهد موند؟
واضح هست که زمانی شرط حلقه ی اول نقض میشه که i=1 بشه یا مقداری کمتر از ۱.
الان بعد از یک بار اجرای حلقه ی دوم که مقدار i بزرگتر از یک هست دوباره شرط while اول درست هست و میایم داخل حلقه.
j=1
$j=3\: ......\: i=\frac{n}{n^{\log_32}\cdot2}$ که i مقدارش از ۱ کمتر میشه. اما این شرط حلقه رو که $j<n$ رو نقض نمیکنه. پس این while دوم هم $\log_3n$ بار اجرا میشه تا از while دوم بیاد بیرون. در این جا مقدار i برابر شده با $\frac{n}{n^{2\log_32}}$
حالا شرط while اول چک میشه. غلط هست چون i از ۱ کوچیکتر هست. پس کلا دو تا $\log_3n$ بار دستورات انجام شد و در نتیجه مرتبه ی زمانی برابر میشه با $\theta(\log_3n)$