[Solved]: Cost at Each Level of a Recursion Tree

Problem Detail: 

Given a recursive function $T(n)=T(a_1\cdot n)+\dots +T(a_k\cdot n)+\Theta(n)$ such that $\forall a_i: 0<a_i<1$, what is the most general thing I can say about the sum of the cost of the nodes at each level of the recursion tree? I've looked at a few, and for the ones I've looked at it's always come out to $(a_1+\dots +a_k)^i$ where $i$ is the level in the tree.

Could anyone explain this? If it matters it's in the context of trying to prove that $T(n)=\Theta(n) \Leftrightarrow a_1+\dots +a_k < 1$

Asked By : Robert S. Barnes

Answered By : Aryabhata

You are right!

The work $W$ at each node (of level $i$), splits into $Wa_1, Wa_2, \dots, Wa_k$ at level $i+1$.

If you add them up, you get that the total work at level $i+1$ is $a_1 + a_2 + \dots + a_k$ times the total work at level $i$.

Of course, this assumes that your $\Theta(n)$ is some exact $cn$, but this argument is good enough to prove that $T(n) = O(n)$. Proving $T(n) = \Omega(n)$ is trivial.

btw, I recommend you look at Akra-Bazzi as a useful tool, if you are interested in such questions.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents