سلام

ببینید، شما i=1 قرار میدهید. بعد به حلقه ی داخلی وارد میشوید. و به اندازه ی i حلقه ی داخلی رو اجرا میکنید.

بعد دقت کنید که خود i میتونه تا n اجرا بشه.

۱)فرض کنیم i=1 باشد.شما j را یک بار اجرا میکنید دستور بعدی آن را هم اجرا کرده از حلقه خارج میشوید.
===
۲)حالا i=2 باشد ، شما از j=1 تا زمانی که j<=2 باشد حلقه ی داخلی را اجرا میکنید. فقط دقت کنید که وقتی در این حلقه میچرخید j هر بار دو برابر می شود. حالا به ازای j=1 شرط برقرار است و یک اجرا داریم.سپس شما j*=2 را انجام دهید که مقدار j=2 میشود. باز هم شرط حلقه برقرار است و یک اجرای دیگر نیز داریم.(این شد دو تا اجرا) در چرخش بعد در داخل همین حلقه شرط دیگر برقرار نیست. و از حلقه خارج میشویم.

۳) سپس i=3 میشود
باز هم به حلقه ی داخلی وارد می شویم.و به ازای j=1 تا زمانی که j<=3 به اجرای حلقه می پردازیم، چون j هر بار دو برابر میشود باز هم با دو اجرا از حلقه داخلی خارج میشویم.

۴)سپس i=4
باز هم به حلقه ی داخلی وارد می شویم و به ازای j=1 تا زمانی که j<=4 به اجرای حلقه می پردازیم داریم، به ازای j=1 شرط برقرار است و یک اجرا داریم، سپس j*=2 میشود و باز هم شرط برقرار است به شکل مقابل ( ۴=>2 ) ، سپس دوباره j*=2 را انجام میدهیم و باز هم شرط برقرار است یعنی داریم ( ۴>=4) ، یعنی سه اجرا به ازای i=4 در دور بعدی از حلقه خارج می شویم . . .

۵)مقدار i=5 الی آخر . . .

به صورت تقریبی میشود حدس زد که ما مجموعِ [tex]\log i[/tex] تا اجرا داریم. با حد بالای n ، چرا که i خودش تا n پیش میرود . . .

زمان اجرا ها به ازای مقادیر i :
[tex]1\: +2+2+3+3\: .\: .\: .[/tex]

همین که در حلقه داخلی j هر بار دو برابر میشود و حد بالای j را i در نظر گرفته ایم یعنی اینکه به اندازه ی مجموع لگاریتم i با حدود i به اجرای حلقه داخلی j می پردازیم.