What is the asymptotic bound? How do you get to the result?
$$T(n)= 3 \cdot T(\sqrt[3]{n})+n^3$$
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Calculate the difference between T(n) and n^3 for n = 2^27. See if that gives you some idea. $\endgroup$– gnasher729Jul 10, 2021 at 13:16
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
The lower bound of $$T(n)\mathcal={\Omega}(n^3).$$ Because of $T(n)$ have a term $n^3.$
To find the upper bound we can use induction: $$T(n)\leq cn^3$$ $$=3cn+n^3\leq cn^3$$ As $n\to \infty$ , and for all $c\geq 3$ $$=3cn+n^3\leq cn^3.\hspace{10pt}\square$$ So $$T(n)=\theta(n^3).$$
$\begingroup$
$\endgroup$
3
Use a change of variable: $n = a^k$, $T(a^k) = t(k)$ gives:
$$t(k) = 3 t(k/3) + a^{3 k}$$
Apply the Master Theorem to this.
-
$\begingroup$ $T(n)=3.T(n^\frac{1}{3})+n^3$ Suppose $n=a^k$ then,$T(a^k)=3.T(a^\frac{k}{3})+a^{3k}$ Assuming, $T(a^k)=S(k)$ we shall have $S(k)=3.S(\frac{k}{3})+a^{3k}$. Why did your $a^{3k}$ become $3k$ $\endgroup$ Jun 10, 2021 at 6:51
-
$\begingroup$ @AbhishekGhosh. Thank you. What math tool do you use to get to this types of equations please? Is it linear recurrence equation? Also, is $S(k/3) = T(a^{k/3})$? What is the advantage of using concise equation every time from $T(n)$ to $S(k)$ please? $\endgroup$– AvvSep 23, 2021 at 19:33
-
$\begingroup$ Yes $S(\frac{k}{3})=T(a^{\frac{k}{3}})$. We use these sort of transformation with a hope that we can convert the recurrence relation into a known form easily solvable by Master Method (a cookbook method). But unfortunately, I guess it cannot be solved using master method. $\endgroup$ Sep 24, 2021 at 8:54
$\begingroup$
$\endgroup$
As
$$ T\left(3^{\log_3n}\right)=3T\left(3^{\log_3 \sqrt[3]{n}}\right)+n^3 $$
making $\mathcal{T}\left(\cdot\right)= T\left(3^{(\cdot)}\right)$ and $z= \log_3 n$ we follow with
$$ \mathcal{T}\left(z\right)= 3\mathcal{T}\left(\frac z3\right)+3^{3z} $$
now with an analog procedure, making $\mathbb{T}\left(\cdot\right)=\mathcal{T}\left(3^{(\cdot)}\right) $ and $\mu = \log_3 z$ we follow with the recurrence
$$ \mathbb{T}\left(\mu\right)=3\mathbb{T}\left(\mu-1\right)+3^{3\cdot 3^{\mu}} $$
now this recurrence has as solution
$$ \mathbb{T}\left(\mu\right)=\frac 13\log_3 \mu\left(c_0+\sum_{k=0}^{u-1}3^{3^{k+2}-k}\right) $$
and now going backwards with $\mu=\log_3 z$ and $z = \log_3 n$ we arrive at
$$ T(n) = \frac 13\log_3 n\left(c_0+\sum_{k=0}^{\log_3(\log_3 n)-1}3^{3^{k+2}-k}\right) $$
now considering $k = \log_3(\log_3 n)-1$ we have for sure
$$ T(n) \ge n^3 $$
