0

I need to prove that the following recurrence relation is $O(5^n)$: $$ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $$ And $T(n)=\Theta(1)$ for $n\le 9$.

I am trying induction, and proving that there exists $c$ such that $T(n)\le c\cdot5^n$, but I am stuck at the induction step:

$T(n)=5^n+3T(\big\lfloor n^\frac{2}{5}\big\rfloor)\le5^n+3c\cdot 5^{\lfloor n^\frac{2}{5}\rfloor}\le5^n+3c \cdot 5^{n^{\frac{2}{5}}}=\bigg(1+\frac{3c}{5^{n- n^\frac{2}{5}}}\bigg)\cdot 5^n$.

How can I continue in the induction (turn the parenthesis into the constant $c$ / is there a different way to prove it?

Daniel
  • 558
  • Do you know the Master theorem? – cgss Jan 08 '21 at 23:41
  • @cgss No, I don't – Daniel Jan 08 '21 at 23:53
  • I would suggest you give it a look. It's a very useful tool for recurrence relations. Check case from the link. It's almost what you need. – cgss Jan 09 '21 at 00:10
  • @cgss Is there a way to prove it without using the Master Theorem? Because we didn't learn it. For example, how can I complete the induction step? – Daniel Jan 09 '21 at 06:58
  • For $n\geq 3$, $$ 1 + \frac{{3 \cdot 2}}{{5^{n - n^{2/5} } }} < 2, $$ so you can take $c=2$. – Gary Jan 09 '21 at 09:12
  • @cgss The master theorem won't work here, he has $T( n^{0.4} )$ which is most certainly not in the form of $aT( \frac{n}{b} )$ ... – CSch of x Jan 26 '21 at 19:57
  • There's a been a while since I checked the problem but if i recall correctly you could work with inequalities and substitute $n^{0.4}$ with $n$ or something similar to make it work. I can always be wrong though. – cgss Jan 27 '21 at 21:53

1 Answers1

1

Considering the recurrence

$$ T(n) = 5^n+3T\left(n^a\right) $$

$$ T\left(a^{\log_a n}\right) = 5^n+3T\left(a^{\log_a n^a}\right) $$

now making $z = \log_a n,\ \ \mathcal{T}(\cdot) = T\left(a^{(\cdot)}\right)$ we follow with

$$ \mathcal{T}(z) = 5^{a^z}+3\mathcal{T}(a z) $$

or

$$ \mathcal{T}(a^{\log_a z}) = 5^{a^z}+3\mathcal{T}(a^{\log_a (a z)}) $$

making now $u = \log_a z,\ \ \mathbb{T}(\cdot) = \mathcal{T}\left(a^{(\cdot)}\right)$ we follow with

$$ \mathbb{T}(u) = 5^{a^{a^u}}+3\mathbb{T}(u+1) $$

This recurrence has the solution

$$ \mathbb{T}(u) =3^{1-u}\left(c_1 - \sum_{k=0}^{u-1}3^{k-1} 5^{a^{a^k}}\right) $$

and going backwards

$$ T(n) = 3^{1-\frac{\ln \left(\frac{\ln (n)}{\ln (a)}\right)}{\ln (a)}}\left(c_1-\sum _{k=0}^{\frac{\ln \left(\frac{\ln (n)}{\ln(a)}\right)}{\ln (a)}-1}3^{k-1} 5^{a^{a^k}}\right) $$

NOTE

With $a = \frac 25$ and $k = \frac{\ln \left(\frac{\ln (n)}{\ln(a)}\right)}{\ln (a)}-1$

$$ 5^{a^{a^k}} = 5^{n^{\frac 52}} $$

Cesareo
  • 33,252