- #1
evinda
Gold Member
MHB
- 3,741
- 0
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 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)
Last edited:
