- #1

evinda

Gold Member

MHB

- 3,836

- 0

I want to find an asymptotic upper bound for the recurrence relation: $T(n)=9T \left (\frac{n}{3} \right ) + n^2 \log n $, $T(n)=c, \text{ when } n \leq 9$, using the following method:

We choose a specific function $f(n)$ and we try to show that for an appropriate $c>0$ and an appropriate $n_0 \in \mathbb{N}$, it stands that $T(n) \leq c f(n)$.

We suppose that $T(k) \leq c f(k), \forall k<n$ and we try to show that it stands for $n$.

Could we do it like that? (Thinking)

$T(n)=9T \left (\frac{n}{3} \right ) + n^2 \log n= \\

9 \cdot ( 9T \left ( \frac{n}{3^2} \right ) + \frac{n^2}{3^2} \log \left ( \frac{n}{3}\right)) +n^2 \log n =

\\ 9^2 T \left ( \frac{n}{3^2} \right )+ 9 \frac{n^2}{3^2} \log \left ( \frac{n}{3}\right) +n^2 \log n=

\\ = \dots =\\

9^i T\left ( \frac{n}{3^i} \right )+ \sum_{j=0}^{i-1} n^2 \log {\frac{n}{3^j}}=\\

9^i T\left ( \frac{n}{3^i} \right )+ n^2 \sum_{j=0}^{i-1} (\log n- j\log 3)= \\

9^i T\left ( \frac{n}{3^i} \right )+ n^2 \log n \sum_{j=0}^{i-1} 1 - \log 3 n^2 \sum_{j=0}^{i-1} j = \\

9^i T\left ( \frac{n}{3^i} \right )+ n^2 \ \log n \ i - \log 3 \ n^2 \ \frac{i(i-1)}{2} $For $i=\log_3 n $:

$T(n)=cn^2+n^2 \ \log n \ \log_3 n-\log 3 \ n^2 \frac{1}{2} (\log_3^2 n-\log_3n) \leq K n^2 \log^2n=O(n^2 \log^2n)$We will show that $T(n)=O(n^2 \log^2n)$.

We suppose that $\exists c>0$ such that $\forall k <n$ $T(k) \leq c k^2 \log^2k$.

$T(n)=9T \left (\frac{n}{3} \right ) + n^2 \log n \leq c n^2 \log^2 \left ( \frac{n}{3} \right ) + n^2 \log n=c n^2 \log^2n -\log^2 3 + n^2 \log n$

Is it right so far? Or have I done something wrong? (Thinking)

Is the substitution method a good way to find a function, in order to apply the method I am asked to use?