Cost at Each Level of a Recursion Tree 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&lt;a_i&lt;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 &lt; 1$
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.