0
$\begingroup$

I'm trying to bound this recurrence with the substitution method. My guess is $O(n^3)$. These are some steps: $$T(n) \leq cn^3 \\ T(n) \leq 27cn^3+n^3$$ How can I continue?

$\endgroup$
2
  • 2
    $\begingroup$ Do you realise that $\frac{27n}{9} = 3n$? $\endgroup$
    – Nathaniel
    Commented Nov 26, 2021 at 16:56
  • $\begingroup$ This question makes no sense, the result will be a negative number. Since the RHS has $T(3n)$ and $3n>n$, you will need to rearrange in order to substitute correctly. After the rearranging it will be clear why the result is negative. $\endgroup$
    – nir shahar
    Commented Nov 26, 2021 at 17:03

2 Answers 2

2
$\begingroup$

I am assuming that the recurrence relation you are trying to solve is: $$T(n) = 27T(n /9) + n^3$$

Using the substitution method, you can prove that for any $k \leqslant \log_3 n$: $$T(n) = 3^{3k}T\left(\frac{n}{3^{2k}}\right) + n^3\sum\limits_{i=0}^{k-1} \frac{1}{27^i}$$

For $k = \log_3n$, we get $T(n) \leqslant n^3T(1) + n^3\sum\limits_{i=0}^{+\infty}\frac{1}{27^i}=n^3(T(1) + \frac{27}{26})$.

Since clearly $T(n) \geqslant n^3$, we conclude that $T(n) = \Theta(n^3)$.

$\endgroup$
0
$\begingroup$

We have T(3n) = T(n) - n^3.

If T(1) = c, then T(3) = c-1, T(9) = c - 28, T(27)=c-757 etc.

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