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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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)$.

Improve this answer
$\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, privacy policy and cookie policy

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