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

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?

• The value of $T(n)$ is certainly polynomial, and its not hard to see that it is bounded by $O(n^{\log_3(5)}\cdot 2n \cdot \log_3(n))$. This is a really rough bound! It is obtained by writing out the entire formula for $T(n)$ as a big summation of values, and swapping all of those values with $5^{\log_3(n)}\cdot 2n$ which is always bigger than them. Sep 21, 2021 at 13:09
• Why do you subtract 1?I think T(n)=5[5T(n/9)+2/3n]+2n..... continue till u reach 5to the power logn base3 +2n(1+5/3+(5/3)²+...) {corrected one mistake of powers of 5 in the nominator}
– ShAr
Sep 21, 2021 at 14:33
• @nirshahar. Thanks! I had lots of mistakes. I corrected them now, what do you think please?
– Avv
Sep 21, 2021 at 16:09

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.

• Thank you very much. Very clear answer. One question please about what you mean by we do much $2n$ "much work" at level 0, then we do $2n/3$ 5 times much work at level 1, ...?
– Avv
Sep 21, 2021 at 16:06
• Second question please, how $2n$ came into the sum above? I can see from the equations I wrote in my question that we have $5^n$ outside $T(\frac{n-(n-1)}{3^n})$, so you injected $5^n$ inside $T$ to get $T(5^n \times \frac{n-(n-1)}{3^n})$ please? But I am not sure how you got again $2n$ please?
– Avv
Sep 21, 2021 at 16:13

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*}

• Thank you very much, but we did not cover linear recurrence formulas though, but your solution is very clear.
– Avv
Sep 21, 2021 at 17:56

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 and we get:

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

• Very clear solution
– Avv
Apr 25 at 14:00

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