0
$\begingroup$

Given recursive equation, $T(n) = 3T(\frac n3 + 5) +\frac n2$

$$ \begin{align} T(n) = 3T(\frac n3 + 5) +\frac n2 \tag{1} \label{1} \\ \lt 3T(n- 15) +\frac n2\\ \lt 3 \left(3T\left(\frac{(n- 15)}{3} +5 \right) + \frac{n-15}{2} \right) + \frac {n}{2} \tag{2}\label{2}\\ \lt 9T(\frac n3) + 3\frac {n-15}{2} + \frac n2 \tag{3}\label{3}\\ \lt 9d_1(\frac n3) \log{\frac n3} + 2n - \frac {45}{2} \tag{4}\label{4}\\ \vdots\\ O(n\log{n}) \end{align} $$

Problem: How we got \ref{4} please unless you want to follow another approach?

$\endgroup$

1 Answer 1

2
$\begingroup$

Define $S(n) = T(n+\alpha)$ for some $\alpha$ to be chosen later. Then:

$$ S(n)=3T\left(\frac{n}{3} + \frac{\alpha}{3}+5\right)+\frac{n+\alpha}{3} = 3S\left(\frac{n}{3} - \frac{2\alpha}{3}+5\right) +\frac{n+\alpha}{3}. $$

Picking $\alpha = \frac{15}{2}$ we get $ S(n) = 3S\left(\frac{n}{3}\right) + \frac{n}{3} + \frac{5}{2} $ and, by the master theorem, we have $S(n) = \Theta(n \log n)$.

We can therefore conclude that $T(n) = S\left(n-\frac{15}{2}\right) = \Theta\left( \left(n-\frac{15}{2}\right) \log \left(n-\frac{15}{2}\right) \right) = \Theta(n \log n)$.

$\endgroup$
4
  • $\begingroup$ Very clear. Thanks. So, how we got please $3S(n/3 -2\alpha/3 + 5)$? Also by master theorem, we know that $f(n) = n^k (\log_b{a})^p$, so from $S(n)$ we see that $k=1$ since we have $n/3$ and $p=0$ is that correct please? I see that you set $\alpha = 15/2$ to get rid of all numbers inside $S(n)$ and to keep only $n/3$. $\endgroup$
    – Avv
    Oct 1, 2021 at 20:02
  • 1
    $\begingroup$ $S(n/3 - 2\alpha/3 +5)$ is equal to $T(n/3 + \alpha/3 +5)$ by the definition of $S$ (recall that $S(n) = T(n+\alpha)$). You have that $f(n) = \Theta(n^{\log_b a} \log^k n)$ where $a=b=3$ and $k=0$. Therefore the solution is $S(n) = \Theta(n^{\log_b a} \log^{k+1} n) = \Theta(n \log n)$. $\endgroup$
    – Steven
    Oct 1, 2021 at 20:17
  • $\begingroup$ Can we say as well that if $T(n) = T(n-1) + 1/n$ that we define $S(n) = T(n+\alpha -1) + 1/(n + \alpha)$? I see from all examples, you are giving very clear solutions, so how you start please when you use the approach you used in this example? Are you following approach where you want to simlify $T(n)$ and also making sure $f(n)$ saves form so that you can apply master method on it? $\endgroup$
    – Avv
    Oct 1, 2021 at 20:58
  • $\begingroup$ You can't use the master theorem on $T(n)=T(n-1)+1/n$ but you can easily see that $T(n)=\sum_{i=1}^n \frac{1}{i} = H_n = \Theta(\log n)$, where $H_n$ is the $n$-th harmonic number. $\endgroup$
    – Steven
    Oct 2, 2021 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.