I'm studying for an entrance exam and I have sample questions. One of the questions is this

Prove that recurrence $T(n) = T(n/5) + T(4n/5)+n/2$ has a solution $T(n) = \omega(n \log n)$.

Solve by drawing the recursion tree.

This is what I drew on my paper:

root:  n/2 => (4n/5)/2

           => (n/5)/2

right sub tree:  (4n/5)/2 => (16n/25)/2

                          => (4n/25)/2

left sub tree:   (n/5)/2  => (4n/25)/2

                          => (n/25)/2

From what I saw online when I was searching for a solution to this question I noticed people were drawing the trees and saying Big O something as an answer. I'm wondering how do they determine that Big O notation is the correct answer for this question or if my tree is correct?

  • $\begingroup$ After expanding the tree a couple of levels and calculating the work done at each level, you should add up the works done at each level and that should give you an upper bound. Sometimes the sequences of works turns out to be a well known sequence. $\endgroup$ – mrk Mar 4 '13 at 15:53
  • 1
    $\begingroup$ An $O$-bound does not prove an $\omega$-bound. $\endgroup$ – Raphael Mar 5 '13 at 7:01

Use the Akra-Bazzi method. In terms of the notation there you have: $$ \begin{align*} g(x) &= \frac{x}{2} = O(x^c) \\ a_i &> 0 \quad \forall i \\ 0 &< b_i < 1 \quad \forall i \\ \end{align*} $$ The requisites check out (and the somehow implied differences $h_i(x)$ due to truncation if the divisions don't come out exact also check out). So we need the $p$ for which: $$ \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1 $$ which is seen to be $p = 1$. Plugging into the equation: $$ T(x) = \Theta \left( x^p \left( 1 + \int_1^x \frac{g(u) d u}{u^{p + 1}} \right) \right) = \Theta (x (1 + \frac{1}{2} \ln x)) = \Theta (x \ln x) $$


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.