Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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)))]$$

share|improve this answer
    
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}.$$

share|improve this answer
    
thanks Marko.. this is more clearer –  VISHNU VIVEK Nov 17 '12 at 13:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.