3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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*} $$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – johnchen902 Mar 22 '14 at 3:24
  • $\begingroup$ You're right, the argument doesn't work... but I believe that an argument along the same lines should. $\endgroup$ – Yuval Filmus Mar 22 '14 at 3:30
  • $\begingroup$ 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$). $\endgroup$ – Yuval Filmus Mar 22 '14 at 3:43
  • $\begingroup$ 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. $\endgroup$ – johnchen902 Mar 22 '14 at 5:46
0
$\begingroup$

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)$.

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

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.