# Solve $T(n) = 3T(\frac n3 + 5) +\frac n2$

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?

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)$$.

• 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$.
– Avv
Oct 1, 2021 at 20:02
• $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)$. Oct 1, 2021 at 20:17
• 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?
– Avv
Oct 1, 2021 at 20:58
• 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. Oct 2, 2021 at 21:32