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


ابتدا تغییر متغیر انجام می دهیم به صورت زیر

[tex]n=2^{k}[/tex]

خواهیم داشت

[tex]T(2^{k})=2T(2^{k/2}) \log_22^{k}[/tex]

رابطه بالا می شود :

[tex]T(2^{k})=2T(2^{k/2}) k[/tex]

برای زیبایی اینگونه تغییر می دهیم :

[tex]g(k)=2g(k/2) k[/tex]

خواهیم داشت :

[tex]g(k)=\theta((k)(\lg k))[/tex]

حال بر حسب n به صورت زیر می شود :

[tex]T(n)=\theta((\lg n)(\lg\lg n))[/tex]