2

Use the substistution method to find an asymptotic upper bound for the relation $$T(n)=3 T\left ( \frac{n}{3}+5 \right )+\frac{n}{2}$$

Try so that the bound is as accurate as possible. Consider that the function $T(n)$ is constant for $n \leq 10$.

$$$$

That's what I've tried:

$$T'(n)=3T' \left (\frac{n}{3} \right )+\frac{n}{2} \tag 1$$

$a=3 \geq 1,\ \ \ b=3 >1$

$f(n)=\frac{n}{2}$ asymptotically positive and increasing

$\displaystyle{n^{\log_b a}=n^{\log_3 3}=n}$

$f(n)=\Theta (n^{\log_b a})$

So, from the Master Theorem (Case 2) :

$$T'(n)=\Theta (n \lg n) \tag 2$$

We suppose that $T(n)=\Theta (n \lg n)$.

So, $\exists c>0$ and $n_0 \geq 1$ such that $\forall n \geq n_0$ $$T(n) \leq cn \lg n \tag 3$$

We suppose that the guess hols also for $\frac{n}{3}+5$, then:

$$T \left ( \frac{n}{3}+5 \right ) \leq c \left ( \frac{n}{3}+5 \right ) \lg \left ( \frac{n}{3}+5 \right ) \tag 4$$

Then:

$$\left ( \lg \left ( \frac{n}{3}+5 \right ) \leq \lg \left ( \frac{2n}{3} \right ), \text{ if } \frac{n}{3}+5 \leq \frac{2n}{3} \Rightarrow 5 \leq \frac{n}{3} \Rightarrow n \geq 15 \right )$$

$$T(n) \leq 3 c \left ( \frac{n}{3} +5 \right ) \lg \left ( \frac{n}{3}+5 \right )+\frac{n}{2} \tag 5 $$ $$\leq c n \lg \left ( \frac{2n}{3} \right )+15 c \lg \left ( \frac{2n}{3} \right )+\frac{n}{2} = cn \left ( \lg n-\lg \left ( \frac{3}{2} \right ) \right ) +15c \left ( \lg n-\lg \left ( \frac{3}{2} \right ) \right )+\frac{n}{2} \tag 6$$ $$ =cn \lg n -cn \lg \left ( \frac{3}{2} \right ) +15 c \lg n-15 c \lg \left ( \frac{3}{2} \right ) +\frac{n}{2} \tag 7 $$ $$ =cn \lg n - \left ( cn \lg 3-cn-15c \lg n+15 c \lg 3-15c-\frac{n}{2} \right ) \tag 8 $$ $$ \leq cn \lg n , \ \text{ if } \ cn \lg 3-cn-15c \lg n+15 c \lg 3-15c-\frac{n}{2} \geq 0 \tag 9$$

$$cn \lg 3-cn-15c \lg n+15 c \lg 3-15c-\frac{n}{2} \geq 0 \tag {10} $$ $$ \Rightarrow c \left ( n \lg 3 -n -15 \lg n+15 \lg 3-15\right ) \geq \frac{n}{2} \tag {11} $$ $$ \Rightarrow c \left ( (n+15) \lg 3 -(n+15)-15 \lg n \right ) \geq \frac{n}{2} \tag {12} $$ $$ \Rightarrow c \left ( (n+15)(\lg 3 -1)-15 \lg n \right ) \geq \frac{n}{2} \tag {13} $$ $$ \Rightarrow c \geq \frac{n}{2 \left ( (n+15)(\lg 3 -1)-15 \lg n \right )} \tag {14} $$ $$ \Rightarrow c \geq \frac{1}{2 \left ( \left ( 1+\frac{15}{n} \right ) \left ( \lg 3 -1\right ) -15 \frac{lg n}{n} \right )} \tag {15}$$

Since $\displaystyle{\frac{15}{n} \overset{n\rightarrow \infty}{\longrightarrow }0}$ and $\displaystyle{15\frac{\lg n}{n} \overset{n\rightarrow \infty}{\longrightarrow }0}$

$$c \geq \frac{1}{2 \left ( \lg 3 -1 \right ) } \tag {16}$$

Is it right? Or have I done something wrong?

evinda
  • 7,823
  • 1
    $\frac{n}{3}+5$ may not be an integer. How do you deal with it? – mike Sep 07 '14 at 15:58
  • 1
    I don't know..It isn't given more information about this..So,is my solution wrong? – evinda Sep 07 '14 at 16:14
  • can you add tags to your equations? so that I can tell you which one might be wrong. – mike Sep 07 '14 at 16:17
  • How do you get this equation $T'(n)=3T' \left (\frac{n}{3} \right )+\frac{n}{2}$? The prime (') stands for differentiation? – mike Sep 07 '14 at 16:23
  • I used $T'(n)$ as a similar relation of $T(n)$ so that I can use the Master Theorem to get a guess for the upper bound of $T(n)$, because I cannot apply it at $T(n)$. – evinda Sep 07 '14 at 16:27
  • but $n/3$ could be a non integer. what do you mean by $T(10/3)$? – mike Sep 07 '14 at 16:32
  • So am I supposed to take constraints like $n$ has to be a multiple of $3$ ? Or do I have to do something else? – evinda Sep 07 '14 at 16:39
  • like take the integer part, or floor, or ceiling, of $n/3$ – mike Sep 07 '14 at 16:41
  • Having found the solution of the relation using integer part, or floor, or ceiling, is the solution the same for the original relation? – evinda Sep 07 '14 at 16:43
  • I do not quite understand how you get the original relation. for n=100, we have $T(100)=3T(5+33+1/3)+50$. but you never calculate $T(5+33+1/3)$ before because the LHS of your original relation always has integer argument. – mike Sep 07 '14 at 16:49
  • 2
    @evinda, it seems correct! I don't think it's necessary to be precise using floor/ceiling functions as their contributions are minor for finding the asymptotic bound and usually it's assume $n/3, n/2$ are integers. Don't worry about that! – Ehsan M. Kermani Sep 07 '14 at 16:53
  • Great!!!Thanks a lot!!! – evinda Sep 07 '14 at 19:14

0 Answers0