How do I prove that $a = n/2$ is a tight upper bound for the recurrence relation $T(n) = T(n-a) + T(a) + n$?

I have a recurrence relation: $$T(n) = T(n-a) + T(a) + n$$

which happens to be $O(n^2)$ complexity.

How do I now prove that:

$$a = n/2$$

is a tight upper bound for this relation? I have been pointed towards the Master Theorem and doing the analysis 'by hand' by substitution $2^k$ into the equation.

Not really sure how to solve this.

Any help would be greatly appreciated, thanks!

• I've got as far as T(2^k) = 2T((2^k)/2) + 2^k . Where do I go from here? Aug 17, 2014 at 4:57
• I can't figure out what you mean by "is a tight upper bound for this relation".
– user14972
Aug 17, 2014 at 5:14

We claim that if: $$T(n) = 2T(n/2) + n$$ then $T(n) = \Theta(n \log n)$. To see this, it suffices to prove by induction on $n$ that there exist constants $c,d,n_0 \geq 1$ such that for all $n \geq n_0$, we have that:

$$cn \log n \leq T(n) \leq dn\log n \tag{\star}$$

Base Case: I'll let you do this part.

Induction Hypothesis: Assume that $(\star)$ holds for all $n' < n$.

It remains to prove that $(\star)$ holds for $n' = n$. Indeed, observe that: \begin{align*} 2T(n/2) + n &= T(n) = 2T(n/2) + n \\ 2(c \tfrac{n}{2}\log \tfrac{n}{2}) + n &\leq T(n) \leq 2(d\tfrac{n}{2} \log \tfrac{n}{2}) + n &\text{by the ind. hyp.} \\ cn(\log n - \log 2) + n &\leq T(n) \leq dn (\log n - \log 2) + n \\ (cn\log n) + (\underbrace{1 - c \log 2}_{\geq~0})n &\leq T(n) \leq (dn \log n) - (\underbrace{d\log 2 - 1}_{\geq~0})n \\ cn \log n &\leq T(n) \leq dn\log n \end{align*} where the last step used the fact that we can choose $c \leq \frac{1}{\log 2}$ and $d \geq \frac{1}{\log 2}$.

• Thank you very much! I'm a little confused on the last step, how exactly does this prove that the upper bound is tight for a= n/2? Aug 17, 2014 at 5:16
• I don't know what you mean by "is a tight upper bound for this relation". I showed that if $a = n/2$, then a tight upper bound for $T(n)$ is $\Theta(n \log n)$. Aug 17, 2014 at 5:17
• Oh I see I see. What would be a better bound for T(n) is Θ(n^2)? Aug 17, 2014 at 5:20
• Both $n \log n$ and $n^2$ are upper bounds for $T(n)$ (that is, $T(n) = O(n \log n)$ and $T(n) = O(n^2)$). But only $n\log n$ is a tight upper bound (that is, $T(n) = \Theta(n \log n)$). Aug 17, 2014 at 5:22
• Ok thank you, I understand that. I am reading a book on Complexity of Algorithms, and the question say that the recurrence relation is O(n^2), and then asks, what is a tight upper bound for O(n^2), if a=n/2 is not tight for O(n^2)? Aug 17, 2014 at 5:24