2
$\begingroup$

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$

|cite|improve this question
$\endgroup$
  • $\begingroup$ Sure $(a_1+\dots +a_k)^i$ is wrong. $\endgroup$ – user742 Apr 29 '13 at 10:04
  • $\begingroup$ 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$. $\endgroup$ – Robert S. Barnes Apr 29 '13 at 10:34
  • $\begingroup$ 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. $\endgroup$ – user742 Apr 29 '13 at 10:46
  • 1
    $\begingroup$ But I stated that all the $ai$ meet the condition $0<a_i<1$... $\endgroup$ – Robert S. Barnes Apr 29 '13 at 13:18
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Robert S. Barnes Apr 29 '13 at 18:42
  • $\begingroup$ @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)$. $\endgroup$ – Aryabhata Apr 29 '13 at 21:57
  • $\begingroup$ 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. $\endgroup$ – Robert S. Barnes Apr 30 '13 at 6:18
  • $\begingroup$ @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... $\endgroup$ – Aryabhata Apr 30 '13 at 6:38
  • $\begingroup$ 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)$? $\endgroup$ – Robert S. Barnes Apr 30 '13 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.