MHB How can I show the inequality?

[evinda]

Hey! (Mmm)

I have to define an asymptotic upper and lower bound of the recursive relation $T(n)=3 T(\frac{n}{3}+5)+\frac{n}{2}$.

Firstly,I solved the recursive relation: $T'(n)=3 T'(\frac{n}{3})+\frac{n}{2}$,using the master theorem:

$$a=3 \leq 1, b=3>1, f(n)=\frac{n}{2} \text{ asymptotically positive and increasing}$$

$$n^{\log_b a}=n$$

We see that : $f(n)=\Theta(n)$

So,from the master theorem: $$T'(n)=\Theta(n \lg n)$$

Then,I supposed that $T(n)=\Theta(n \lg n)$, so $\exists c_1, c_2>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0: c_1 n \lg n \leq T(n) \leq c_2 n \lg n$

I showed that the inequality $c_1 n \lg n \leq T(n)$ is true..But..how can I show the inequality :

$$T(n) \leq c_2 n \lg n $$
?

I tried this:

Suppose that the inequality stands for $\frac{n}{3}+5$.Then: $$T(\frac{n}{3}+5) \leq c_2 (\frac{n}{3}+5) \lg (\frac{n}{3}+5)$$

$$T(n)=3 T(\frac{n}{3}+5)+\frac{n}{2}\leq 3 c_2 (\frac{n}{3}+5) \lg (\frac{n}{3}+5)+\frac{n}{2}=c_2(n+15) \lg (\frac{n}{3}+5)+\frac{n}{2} $$

How can I continue? (Thinking) (Thinking)

 

[evinda]

Could we show it maybe like that?

$$T(n) \leq c_2(n+15) \lg (\frac{n}{3}+5)+\frac{n}{2}$$

Let $\frac{n}{3}+5 \leq \frac{n}{2} \Rightarrow n \geq 30$

Then $\forall n \geq 30:$

$$T(n) \leq c_2(n+15) \lg (\frac{n}{3}+5)+\frac{n}{2} \leq c_2(n+15) \lg (\frac{n}{2})+n = c_2 n \lg (\frac{n}{2})+15 c_2 \lg (\frac{n}{2})+n =c_2 n \lg n-(c_2 n-15c_2 \lg n+15 c_2-\frac{n}{2}) \leq c_2 n \lg n, \text{ if } c_2 n-15c_2 \lg n+15 c_2-\frac{n}{2} \geq 0$$

(Thinking)