0
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – nir shahar
    Sep 21, 2021 at 13:09
  • 3
    $\begingroup$ 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} $\endgroup$
    – ShAr
    Sep 21, 2021 at 14:33
  • $\begingroup$ @nirshahar. Thanks! I had lots of mistakes. I corrected them now, what do you think please? $\endgroup$
    – Avv
    Sep 21, 2021 at 16:09

4 Answers 4

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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, ...? $\endgroup$
    – Avv
    Sep 21, 2021 at 16:06
  • $\begingroup$ 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? $\endgroup$
    – Avv
    Sep 21, 2021 at 16:13
1
$\begingroup$

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

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

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

$\endgroup$
1
  • 1
    $\begingroup$ Very clear solution $\endgroup$
    – Avv
    Apr 25 at 14:00
1
$\begingroup$

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

$\endgroup$

Your Answer

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

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