[Solved]: Solve a recurrence by drawing the recursion tree?

Problem Detail: 

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?

Asked By : imGreg

Answered By : vonbrand

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) $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10242