تابع مورد نظر :

[tex]T(n)=T(\sqrt{n}) 1[/tex]



از تغییر متغیر زیر استفاده می کنیم :
[tex]n=2^{2^k}[/tex]

بنابراین خواهیم داشت :
[tex]T(2^{2^k})=T(2^{2^{k-1}}) 1[/tex]

برای سهولت و زیبایی به صورت زیر می نویسیم :
[tex]M(k)=M(k-1) 1[/tex]

مرتبه [tex]M(k)[/tex] برابر است با [tex]\theta(k)[/tex]

حال باید k به n تبدیل شود :
[tex]n=2^{2^k}[/tex]
[tex]\lg n\: =2^k[/tex]
[tex]\lg\lg n\: =\: k[/tex]

بنابراین مرتبه تابع آغازین برابر است : [tex]\theta(\lg\lg n)[/tex].

سلام جناب موریس میشه بیزحمت برام توضیح بدید چرا بعضی جاها در روش تغییر متغیر [tex]n=2^k[/tex] و در بعضی جاها [tex]n=2^{2^k}[/tex]
بعد اینک چرا به جای K ب توان ۱/۲ نوشتید K-1



من تو این مبحث مشکل دارم ممنون میشم راهنمایی کنید