Solve the worst case of this recurrence equation
For starters, let's rewrite the recurrence as
$$ T(n) \leq \max \sum_{i&gt;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) &gt; T(a) + T(b)$.

Proof. Choose the $a_i,b_j$ for which
$$
\begin{align*}
T(a) &amp;= \sum_{i=1}^k T(a_i) + a + \log k \sum_{i=1}^k a_i, \\
T(b) &amp;= \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 &gt; 0$, and so
$$
\begin{align*}
T(a+b) &amp;\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) \\
&amp;&gt; T(a) + T(b).
\end{align*}
$$