سلام
برای حل این تست باید با تابع لگاریتمی تکراری اشنایی داشته باشید
[tex]\lg^{\ast}n=\min\{i\ge0\: :\: \lg^{(i)}n\le1\}[/tex]
اگر به رابطه بازگشتی [tex]T(n)[/tex]نگاه کنید هر بار از ارگومان رابطه لگاریتم گرفته می شود تا زمانی که مقدار ارگومان به یک برسه (برای این تست شرط توقف رابطه به ازای ورودی یک که مقدار یک تولید می کند می باشد)رابطه تکرار می شه این همون [tex]\lg^{_{\ast}}n[/tex] .یعنی تعداد تکرار تا رسیدن به شرط توقف برابر با تعداد باری که لگاریتم می گیرم تا به یک برسیم که هزینه هر تکرار هم ثابت است پس رابطه بازگشتی از مزتبه [tex]O(\lg^{\ast}n)[/tex]
اگر متوجه نشدید در بعضی منابع[tex]\lg^{\ast}n[/tex] به صورت زیر هم تعریف می شود
[tex]\lg^{\ast}n=0\: \: \: \: if\: \: n\le1[/tex]
[tex]\lg^{\ast}n=1+\lg^{\ast}(\lg n)\: \: \: if\: \: n>1[/tex]
حالا به شباهت تابع [tex]\lg^{\ast}[/tex] و T دقت کنید.