Proving $T(n)=O(n^2 \lg^2 n)$ Using Recurrence Relation

[evinda]

Hello! (Wave)

I want to prove that $T(n)=4 T \left ( \frac{n}{2}\right )+n^2 \lg n=O(n^2 \lg^2 n)$,where $T(n)$ is constant for $n \leq 8$, 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$."

That's what I have tried:

We suppose that :
$$T(k) \leq c k^2 \lg^2 k, \forall k<n$$

$$T(n)=4 T \left ( \frac{n}{2}\right )+n^2 \lg n \leq 4c \left ( \frac{n}{2}\right )^2 \lg^2 \left ( \frac{n}{2}\right )+n^2 \lg n=cn^2 (\lg n-1)^2+n^2 \lg n=cn^2(\lg^2 n-2 \lg n+1)+n^2 \lg n \Rightarrow c \geq \frac{-\lg n}{1-2 \lg n} \to \frac{1}{2}$$

So, the relation stands $\forall c \geq \frac{1}{2}$.

Is it right or have I done something wrong? (Thinking)

 

[I like Serena]

Hello! (Wave)

I want to prove that $T(n)=4 T \left ( \frac{n}{2}\right )+n^2 \lg n=O(n^2 \lg^2 n)$,where $T(n)$ is constant for $n \leq 8$, 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$."

That's what I have tried:

We suppose that :
$$T(k) \leq c k^2 \lg^2 k, \forall k<n$$

$$T(n)=4 T \left ( \frac{n}{2}\right )+n^2 \lg n \leq 4c \left ( \frac{n}{2}\right )^2 \lg^2 \left ( \frac{n}{2}\right )+n^2 \lg n=cn^2 (\lg n-1)^2+n^2 \lg n=cn^2(\lg^2 n-2 \lg n+1)+n^2 \lg n \Rightarrow c \geq \frac{-\lg n}{1-2 \lg n} \to \frac{1}{2}$$

So, the relation stands $\forall c \geq \frac{1}{2}$.

Is it right or have I done something wrong? (Thinking)

Hi! (Smile)

It is right! (Nod)

 

[evinda]

Hi! (Smile)

It is right! (Nod)

Nice! Thank you! (Clapping)