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\quadwhere\quad n=1+\sum_{i=0}^ka_i\quad and\quada_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$.
Solve the worst case of this recurrence equation
asymptotics;recurrence relation