2
$\begingroup$

What is the asymptotic bound? How do you get to the result?

$$T(n)= 3 \cdot T(\sqrt[3]{n})+n^3$$

$\endgroup$
1
  • $\begingroup$ Calculate the difference between T(n) and n^3 for n = 2^27. See if that gives you some idea. $\endgroup$
    – gnasher729
    Commented Jul 10, 2021 at 13:16

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Commented 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$
    – Avv
    Commented Sep 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$ Commented Sep 24, 2021 at 8:54
0
$\begingroup$

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

$\endgroup$

Your Answer

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

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