# How to solve this recurrence $T(n)= 7 T (n/2) + 2 \log (n)$?

Solve this recurrence equation $T(n)= 7T (n/2) + 2 \log (n)$?

Could you please help me to solve it because I have been stuck on it for 2 nights.

Thanks in advance.

-
By checking one of the several quite similar questions listed under the heading Related in a column on the right of the present page. –  Did Nov 11 '12 at 23:52

## 1 Answer

This question's answer should give you a good idea of how to attack these problems. The basic idea is to look at the tree of computations. The top level of the tree gives a contribution of of $2\log n$. The next level will involve 7 contributions of $2\log(n/2)$ for a total of $7\cdot 2(\log n-\log2)$. At the next level, you'll have $7^2$ contributions of $7^2\cdot 2(\log(n/4))=7^2\cdot2(\log n-2\log 2)$. Continue this until you run out of levels (when will that be?) and you'll have a total contribution equal to something involving two series: one is easy and the other will involve a sum that you may or may not have seen, but which is explained in the answers of the link.

As a check, the solution to your recurrence turns out to be $$T(n)=n^{\log_2 7}\left(T(1)+\frac{7\log 2}{18}\right)-\frac{\log 2}{18}\log_2 n-\frac{7\log 2}{18}$$ which, if you're a glutton for punishment, you can verify by induction.

-
Now, I can understand the whole idea about this question Thank you so much Mr.Rick Decker for your effort....I appreciate it –  Abdalrrhman Alahmady Nov 12 '12 at 5:16