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

• Sure $(a_1+\dots +a_k)^i$ is wrong. – user742 Apr 29 '13 at 10:04
• Well, more specifically it's come out to $(a_1+\dots +a_k)^i \cdot \Theta(n)$. But like I said, that's only the trees I've looked at, specifically the ones where $a_1+\dots +a_k<1$. – Robert S. Barnes Apr 29 '13 at 10:34
• No is more closer to this: $[{1 \over a_1 } + ... + {1\over a_k}]^i$, it's a little bit complicated, but if you want prove the other thing, seems you don't need this. – user742 Apr 29 '13 at 10:46
• But I stated that all the $ai$ meet the condition $0<a_i<1$... – Robert S. Barnes Apr 29 '13 at 13:18

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.

• So this only holds when all the $a_i$ are between $0$ and $1$, correct? Also, does this still hold for any function $\Theta(n^x)$? It seems that it would, but I'm not sure. – Robert S. Barnes Apr 29 '13 at 18:42
• @RobertS.Barnes: It(the upper bound proof) will work for any $a_i$, as long as the extra term is $\theta(n)$. No, it won't work for any $\theta(n^x)$. – Aryabhata Apr 29 '13 at 21:57
• I'm not sure I understand. If the $a_i$ sum to a value $\geq 1$, then the algorithm will be at least $\cal{O}(n \lg n)$, since at least $n$ work is being done at each level of the tree. – Robert S. Barnes Apr 30 '13 at 6:18
• @RobertS.Barnes: Yes, I am talking about the proof that work done at each level is $(a_1 + a_2 + \dots + a_k)^{i} \times \Theta(n)$. That does not contradict the fact that $T(n) = T(0.5n)+T(0.5n) + \Theta(n)$ is $\Theta(n \log n)$. Why do you think it does? Perhaps we are talking different things... – Aryabhata Apr 30 '13 at 6:38
• OK, I think I just misunderstood you. I know it's not part of the original question, but why does it only hold when the extra term is $\Theta(n)$ and not for any extra term $\Theta(n^x)$? – Robert S. Barnes Apr 30 '13 at 6:54