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.

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.

share|improve this question
4  
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 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.

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

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.