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

1,491

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

Share:
1,491

Related videos on Youtube

Barney Chambers
Author by

Barney Chambers

Professional wedding photographer on weekends, C# programmer during the week, crypto-coin enthusiast the rest of the time!

Updated on August 17, 2020

Comments

  • Barney Chambers
    Barney Chambers about 3 years

    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!

    • Barney Chambers
      Barney Chambers about 9 years
      I've got as far as T(2^k) = 2T((2^k)/2) + 2^k . Where do I go from here?
    • Admin
      Admin about 9 years
      I can't figure out what you mean by "is a tight upper bound for this relation".
  • Barney Chambers
    Barney Chambers about 9 years
    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?
  • Adriano
    Adriano about 9 years
    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)$.
  • Barney Chambers
    Barney Chambers about 9 years
    Oh I see I see. What would be a better bound for T(n) is Θ(n^2)?
  • Adriano
    Adriano about 9 years
    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)$).
  • Barney Chambers
    Barney Chambers about 9 years
    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)?