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.
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.
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.