# Solve the worst case of this recurrence equation

I am trying to find the worst case $Θ$ bound for the following recurrence equation: $$T(n)=\sum_{i=1}^kT(a_i)+n+\lg k\sum_{i=1}^ka_i\quad where\quad n=1+\sum_{i=0}^ka_i\quad and\quad a_0\ge a_1, a_2, \dots,a_k\ge 1$$ By master theorem, with $k=a_0=a_1=n/3$ and $a_2=a_3=\dots =a_k=1$, $T(n)=Θ(n\lg n)$. Now my freind and I guessed that the worst case of $T(n)$ is also $Θ(n\lg n)$, but we are not able to prove it.

My question is, what is the worst case bound of $T(n)$ and how to prove it?

Edit: By worst case I mean that $T(n)$ to be the maximum of the expression I wrote over all $k\ge1$ and $a_0\ge a_1,a_2,\dots,a_k\ge1$ such that $n=1+a_0+\dots+a_k$.

For starters, let's rewrite the recurrence as $$T(n) \leq \max \sum_{i>0} T(a_i) + O(n\log n).$$ Suppose now that we could show that $T(m+1) - T(m)$ is increasing in $m$. In this case, it follows that we can assume that $a_2 = \cdots = a_k = 1$, and so $$T(n) \leq \max T(a_1) + O(n\log n).$$ The largest that $a_1$ can get is $n/2$ (well, $(n-1)/2$), and so $$T(n) \leq T(n/2) + O(n\log n).$$ Expanding this, we get $T(n) = O(n\log n)$.

Showing that $T(m+1) - T(m)$ (if this is indeed true) looks a bit messy, but potentially could be done in the spirit of the following lemma.

Lemma For all $a,b \geq 1$, we have $T(a+b) > T(a) + T(b)$.

Proof. Choose the $a_i,b_j$ for which \begin{align*} T(a) &= \sum_{i=1}^k T(a_i) + a + \log k \sum_{i=1}^k a_i, \\ T(b) &= \sum_{j=1}^\ell T(b_j) + b + \log l \sum_{j=1}^\ell b_j. \end{align*} Consider the sequence $c_0 = a_0+b_0$, $c_1,\ldots,c_t = a_1,\ldots,a_k,b_1,\ldots,b_\ell,1$, where $t = k+\ell+1$. This sequence sums to $a+b-1$ and satisfies $c_0 \geq c_r \geq 1$ for all $r > 0$, and so \begin{align*} T(a+b) &\geq \sum_{i=1}^k T(a_i) + \sum_{j=1}^\ell T(b_j) + T(1) + a+b + \log(k+\ell+1) \left(\sum_{i=1}^k a_i + \sum_{j=1}^\ell b_j + 1\right) \\ &> T(a) + T(b). \end{align*}

• You claimed that $\max \sum_{i>0} T(a_i) + n + \log k \sum_{i>0} a_i \le T(n/2) + O(n\log n)$, but I don't think $\sum_{i>0}a_i\le n/2$. Can you explain more? – johnchen902 Mar 22 '14 at 3:24
• You're right, the argument doesn't work... but I believe that an argument along the same lines should. – Yuval Filmus Mar 22 '14 at 3:30
• Here is what I had in mind. It is conjectural at this stage – you could try proving the missing lemma. It is enough for $T(m+1) - T(m)$ to be increasing for large enough $m$ (in case it fails for stupid reasons for small $m$). – Yuval Filmus Mar 22 '14 at 3:43
• Assume that $cn\log n\le T(n)\le dn\log n$ for some constant $c, d$ and $2d<3c$, then let $k=3c$, $a_1=\dots=a_{2d}=n/3c, a_{2d+1}=\dots=a_k=1$, then $T(n)\ge2dT(n/3c)+O(n\log n)\ge$ $(2/3)dn\log n+O(n\log n)\gt(1/2)dn\log n+O(n\log n)\ge T(n/2)+O(n\log n)$, which leads to contradiction in your proof (though I can't explain the assumption $2d<3c$). I don't think we can assume that $a_2=\dots=a_k=1$ so fast. – johnchen902 Mar 22 '14 at 5:46

From the division-into-2 case, I'd guess that the worst case is the most unequal division possible, i.e., $a_0 = n - k$ and $a_1 = \ldots = a_k = 1$. Let's check: $$T(n) = T(n - k) + k T(1) + n + k \lg k$$ This gives $T(n) = O(n^2)$.

• It's $T(n)=\sum_{i=1}^kT(a_i)+...$, not $T(n)=\sum_{i=0}^kT(a_i)+...$. – johnchen902 Mar 22 '14 at 0:39