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
    $\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$ – Did Nov 11 '12 at 23:52

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.

| cite | improve this answer | |
  • $\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$ – Abdalrrhman Alahmady Nov 12 '12 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.