0
$\begingroup$

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!

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Aug 17, 2014 at 5:16
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Adriano
    Aug 17, 2014 at 5:17
  • $\begingroup$ Oh I see I see. What would be a better bound for T(n) is Θ(n^2)? $\endgroup$ Aug 17, 2014 at 5:20
  • 1
    $\begingroup$ 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)$). $\endgroup$
    – Adriano
    Aug 17, 2014 at 5:22
  • $\begingroup$ 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)? $\endgroup$ Aug 17, 2014 at 5:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .