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.
$\begingroup$
$\endgroup$
1
-
4$\begingroup$ By checking one of the several quite similar questions listed under the heading Related in a column on the right of the present page. $\endgroup$– DidNov 11, 2012 at 23:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Nov 12, 2012 at 3:56
-
$\begingroup$ Now, I can understand the whole idea about this question Thank you so much Mr.Rick Decker for your effort....I appreciate it $\endgroup$ Nov 12, 2012 at 5:16