Substitution Method

Solve the following recurrence using Substitution Method :

\(\begin{equation} T(n) = \begin{cases} 1 & n \leq 4 \\ 2T(\sqrt n) + \frac{logn} {loglogn} & n>4 \end{cases} \end{equation}\)

 

 

1Comment
Habib Mohammad Khan @habibkhan 4 Sep 2016 05:29 pm

Let n = 2, so logn = k ...........(1)

Applying this in original equation we have, and say S(k) = T(2k) = T(n)

             S(k) = 2S(k/2) + k/logk                                                                                                                             ⇒  S(k) = 2(2S(k/4) + k/2log(k/2)) + k/logk = 22S(k/22) + k/log(k/2) + k/logk

        ⇒  S(k) = k[1/logk + 1/log(k/2) + 1/(log(k/4) + ..............]

Now let us take all the terms to be 1/logk for easier calculation.

                     = k[1/logk +.........k terms] { Since roughly k terms are there}

                     = k2/logk

Hence S(k)  =  k2/logk 

 (or)     T(n) = (logn)2/loglogn