0
$\begingroup$

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.

  • 4
    $B$y checking one of the several quite similar questions listed under the heading **Related** in a column on the right of the present page.2012-11-11

1 Answers 1

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.

  • 0
    Now, I can understand the whole idea about this question Thank you so much Mr.Rick Decker for your effort....I appreciate it2012-11-12