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

$T(n)=T(\sqrt{n}) 1$



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

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

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

مرتبه $M(k)$ برابر است با $\theta(k)$

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

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

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



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