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
