# Solve the recurrence $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log(\log n)}$

I've been trying to solve this recurrence relation in my advance algorithms paper. I've found that the Master method doesn't work.

I tried using an iterative method up to an extent, and then substituted $n = 2^{2^i}$ as below

http://postimage.org/image/624p28vn5/

Please can someone suggest a way to solve it. Any other method that works would also be appreciated!

-

Let $n=k2^i$ Therefore we get:$$T(k2^i)=2T(k2^{i-1})+(k2^i)/\log(\log k+i\log(2))$$

Now multiply both sides by $2^{-i}$ to get: $$2^{-i}T(k2^i)=2^{-(i-1)}T(k2^{i-1})+k/\log(\log k+i\log(2))$$ $$2^{-i}T(k2^i)-2^{-(i-1)}T(k2^{i-1})=k/\log(\log k+i\log(2))$$

Now sum both sides of the equation from i=1 to i=n and use the method of differences.

The solution:$$T(k2^n)=2^{n}[T(k)+\sum\limits_{i=1}^{n}k/\log(\log k+i\log(2))]$$

In case k=1, the solution becomes:$$T(2^n)=2^{n}[T(1)+\sum\limits_{i=1}^{n}1/(\log(i)+\log(\log(2)))]$$

-
Thanks for your quick response Amr. But I'm just a noob in this subject. Actually this problem was supposed to be solved in under 3 minutes. If you could give me the final solution, it would be great. – Vishnu Vivek Nov 16 '12 at 19:26
I edited my answer to include a solution. – Amr Nov 16 '12 at 19:32

Actually the Master method does apply here and it predicts that $$T(n) \sim \frac{n}{\log\log n} \log_2 n \sim \frac{n}{\log\log n} \log n .$$ We pick up the logarithmic factor because the number of subproblems ($2$) times the size of the subproblems is $n$.

It can also be done from first principles. First unwind the recursion to get $$T(n) \sim n \left( \frac{1}{\log(\log n - \log 2^0)} + \frac{1}{\log(\log n - \log 2^1)} + \frac{1}{\log(\log n - \log 2^2)} + \cdots \right)$$ The inner term is the sum $$\sum_{k=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\log(\log n - k \log 2)}.$$ Flip the index variable of the summation to obtain $$\sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{1}{\log(\log n - \lfloor \log_2 n \rfloor \log 2 + k \log 2)}.$$ Now note that $\left| \log n - \lfloor \log_2 n \rfloor \log 2\right| \le \log 2$ so that this is asymptotic to $$\sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{1}{\log\log 2 + \log(1 + k)} \sim \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{1}{\log(1 + k)}.$$

We need the asymptotics of $\sum_{k=1}^m \frac{1}{\log(1 + k)}.$ We have a lower and an upper bound. $$\sum_{q=0}^{\lfloor \log_2 m \rfloor} \sum_{k=2^q}^{2^{q+1}-1} \frac{1}{\log(1 + k)} \le \sum_{k=1}^m \frac{1}{\log(1 + k)} \le \sum_{q=0}^{\lfloor \log_2 m \rfloor + 1} \sum_{k=2^q}^{2^{q+1}-1} \frac{1}{\log(1 + k)}.$$ We simplify these to obtain $$\sum_{q=0}^{\lfloor \log_2 m \rfloor} \frac{2^q}{\log 2^{q+1}} < \sum_{k=1}^m \frac{1}{\log(1 + k)} < \sum_{q=0}^{\lfloor \log_2 m \rfloor + 1} \frac{2^q}{\log 2^q}.$$ or $$\sum_{q=0}^{\lfloor \log_2 m \rfloor} \frac{2^q}{(q+1)\log 2} < \sum_{k=1}^m \frac{1}{\log(1 + k)} < \sum_{q=0}^{\lfloor \log_2 m \rfloor + 1} \frac{2^q}{q \log 2}.$$ These two bounds show that $$\sum_{k=1}^m \frac{1}{\log(1 + k)} \sim \sum_{q=0}^{\lfloor \log_2 m \rfloor} \frac{2^q}{q}.$$ To conclude note that $$\sum_{q=0}^{\lfloor \log_2 m \rfloor + 1} \frac{2^q}{q} \sim \frac{2^{\lfloor \log_2 m \rfloor}}{\lfloor \log_2 m \rfloor} \sim \frac{m}{\log_2 m}.$$ This is because a sum of exponentials is its own asymptotic expansion, since with $S = \sum_{q=1}^p \frac{z^q}{q}$ we have $$\lim_{z\to\infty} \frac{S - \sum_{q=q_0}^p \frac{z^q}{q}}{z^{q_0}/q_0} = \lim_{z\to\infty} \sum_{q=1}^{q_0-1} z^{q-q_0}{q} \frac{q_0}{q} = 0.$$ Finally recall that in our case we have $$m = \lfloor \log_2 n \rfloor$$ to obtain $$T(n) \sim n \frac{\log_2 n}{\log_2 \log_2 n} = n \frac{\log n}{\log \log_2 n} = n \frac{\log n}{\log \log n - \log \log 2} \sim n \frac{\log n}{\log \log n}.$$

-
thanks Marko.. this is more clearer – Vishnu Vivek Nov 17 '12 at 13:39