Solving recurrence relation $T(n) = 5T(\frac{n}{3}) + 2n$

Question

This is not a difficult problem, but I would like please to discuss with you how I solved it:

Solving recurrence relation $T(n) = 5T(\frac{n}{3}) + 2n$, $T(1)=2$. What is the value of $T(9)$? This can be done directly by applying $T(9)$ to get 98. However, I did it recursively as follows:

$$ \begin{align} T(n) = 5\left[5T(\frac{n-1}{3^2}) + 2(n-1)\right] + 2n \tag{1} \\ T(n) = 5\left[5\left[5T(\frac{n-2}{3^3}) + 2(n-2)\right] + 2(n-1)\right] + 2n\\ = 5^3 T(\frac{n-2}{3^3}) + 5^2\times2(n-2) + 5\times2(n-1) + 2n \tag{2} \\ \vdots\\ T(n) = 5^n \times T\left(\frac{n-(n-1)}{3^n}\right) + 5^{n-1}\times2(n-(n-1)) + \cdots 5\times2(n-1) + 2n \tag{3} \\ \end{align} $$

Question: what is the value of $T(n)$ above please as we have $n$, so we can not infinite apply geometric series I guess please?

Answer 1

You can use either the master theorem or use unrolling to solve this.

If you want to apply unrolling, we note that at level 0 of our recursion tree, we do $2n$ much work, at level 1, we do $2n/3$ much work $5$ times. Let's write it as $2 \frac{n}{3^1}$ and we do it $5^1$ times.

At level 2 we do $2 \frac{n}{3^2}$ and we do it $5^2$ times. As you can see, at level $\ell$ we must do $2 \frac{n}{3^\ell}$ much work $5^\ell$ times.

The height of the recursion tree is bounded by $\log_3 n$, so this is a geometric series $$\sum_{\ell=0}^{\log_3 n} 2n \frac{5^j}{3^j} = 2n \sum_{\ell=0}^{\log_3 n} \frac{5^j}{3^j} = \Theta\left(n \cdot \frac{5^{\log_3 n}}{3^{\log_3 n}}\right) = \Theta\left( 5^{\log_3 n} \right) = \Theta\left( n^{\log_3 5} \right).$$

Beware of mistakes.

Answer 2

Change variables: $n = 3^k$, $t(k) = T(3^k)$. In terms of those variables:

$\begin{align*} t(k) &= 5 t(k - 1) + 2 \cdot 3^k \\ t(0) &= t_0 \end{align*}$

The above is just a linear recurrence of the first order, thus easy to solve:

$\begin{align*} t(j + 1) &= 5 t(j) + 6 \cdot 3^{j + 1} \\ \frac{t(j + 1)}{5^{j + 1}} - \frac{t(j)}{5^j} &= 6 \left(\frac{3}{5} \right)^{j + 1} \\ \frac{t(k)}{5^k} - \frac{t(0)}{5^0} &= 6 \frac{3}{5} \sum_{0 \le j < k} \left(\frac{3}{5}\right)^j \\ &= \frac{18}{5} \frac{1 - (3/5)^k}{1 - 3/5} \\ t(k) &= \frac{18}{5 \cdot 2} \cdot 5^k \cdot \left(1 - \left(\frac{3}{5}\right)^k\right) \\ &= \frac{9}{5} (5^k - 3^k) \\ T(n) &= \frac{9}{5} (5^{\log_3 n} - n) \\ &= \frac{9}{5} (n^{\log_3 5} - n) \end{align*}$

Answer 3

I think, as it says Shar you have a mistake, given that:

\begin{aligned} T(n)&=5T(\frac{n}{3})+2n\\ &=5\big ( 5T(\frac{\frac{n}{3}}{3})+2\frac{n}{3} \big )+2n\\ &\neq 5\left[5T(\frac{n-1}{3^2}) + 2(n-1)\right] + 2n \\ \end{aligned}

let's call $a=\frac{1}{3}$, then we rewrite the recurrence as $$T(n)=5T(an)+2n $$ Now let's solve (to do it exactly you must calculate the sum of the m terms):

\begin{aligned} T(n)&=5T(an)+2n \\ &=5\Big (5 \big (T(a^2n)+2an \Big )+2n\\ &=5\Big (5\big(5T(a^3n)+a^2n\big)+2an \Big )+2n\\ &\vdots\\ &=5^mT(a^m n)+ 2n\sum_{i=0}^{m-1}(a^i) \text{ , where } |a|<1\\ &=5^mT(a^m n)+2n\frac{1-a^m}{1-a}\\ \end{aligned} since the base case is $T(1)=2$, let's stop the recursive calls when $a^{m}n\leq 1<a^{m-1}n$ and we get:

$$T(n)=5^m\cdot 2+2n\frac{1-a^m}{1-a}$$

Answer 4

$T(n) = 5T(n/3) + 2n$ ---- (1)

$5T(n/3) = 5^2T(n/3^2) + 2n(5/3)$ ---- (2) [substitute $n/3$ for $n$ in previous equation and then multiply both sides by 5]

$5^2T(n/3^2) = 5^3T(n/3^3) + 2n(5/3)^2$ ---- (3)

$5^3T(n/3^3) = 5^4T(n/3^4) + 2n(5/3)^3$ ---- (4)

$\vdots$

$5^{k-1}T(n/3^{k-1}) = 5^kT(n/3^k) + 2n(5/3)^{k-1}$ ---- (k)

Adding the above $k$ equations:

$T(n) = 5^kT(n/3^k) + 2n + 2n.(5/3)^1 + 2n.(5/3)^2 + 2n.(5/3)^3 + \dots + 2n.(5/3)^{k-1}$ as $n=3^{k}$

$T(n) = 5^kT(1) + 2n(1 + 5/3 + (5/3)^2 + (5/3)^3 + .....(5/3)^{k-1})$ where $k = log_3 (n)$

$ = 5^{log_3 (n)}.c + 2n[(5/3)^{log_3 (n)} - 1]/(2/3)$

$ = c.n^{log_3 (5)} +3n[(5/3)^{log_3 (n)} - 1]$

$ = O(n^{log_3 (5)}+n(5/3)^{log_3 (n)})$

$ = O(n^{1.465}+n(n)^{log_3 (5/3)})$

$ = O(n^{1.465}+n^{1+log_3 (5/3)})$

$ = O(n^{1.465}+n^{1.465})$

$ = O(n^{1.465})$ or $O(n^{log_3 (5)})$