Can anyone explain how to find the $\Theta()$ of this equation... $$T(n) = 3T(n-4) + cn$$ When I solve this problem I get this using the $k$ -th iteration... $$T(n) = 3^{k}T(n-4k) + 3^{k-1}c(n-2(k-1)) + 3^{k-2}c(n-2(k-2)) + ... + cn$$ I factor out c and get this... $$T(n) = 3^{k}T(n-2k) + c(3^{k-1}(n-2(k-1)) + 3^{k-2}(n-2(k-2)) + ... n)$$ I'm not sure if we need to find an upper and lower bounds or solve the geometric series. Any suggestions? I need to find $\Theta()$ and we didn't cover master theorem so this is how my class was taught to approach these.
1
-
$\begingroup$ See also our reference question. $\endgroup$– Raphael ♦Apr 27, 2015 at 11:39
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
The answer should be $\Theta(3^{n/4})$. You can go both ways you suggest – find an exact formula, or estimate the sum, using an integral or in more devious ways. There is no loss in generality if you take $c = 1$. If you replace $n$ with $1$ (so we get a lower bound), then we have $$ 1 + 3 + 3^2 + \cdots + 3^{n/4} = \Theta(3^{n/4}), $$ using the formula for summing a geometric series. If you bring back the $n$, the calculation becomes a bit more difficult, but you should still be able to get a matching upper bound: $$ n + 3(n-4) + 3^2(n-8) + \cdots + 3^{n/4}(0) = O(3^{n/4}). $$ There are in fact closed formulas for this kind of sum (try Wolfram alpha), but you can also try to bound without them, say by looking at ratios of consecutive terms and comparison to a geometric series: $$ 3^{n/4} \left(0 + 4\frac{1}{3} + 8\frac{1}{9} + 12\frac{1}{27} + \cdots \right) = O(3^{n/4}), $$ since the infinite series $4\sum_{m=0}^\infty \frac{m}{3^m}$ converges.
answered Apr 26, 2015 at 16:02
-
$\begingroup$ That's what I got too. It seems like this will converge being infinite. Does this mean that constant factors that aren't the same as the value of n will cause different run times? $\endgroup$– MD_90Apr 26, 2015 at 20:04
-
$\begingroup$ The constant could depend on the residue of $n$ module 4. $\endgroup$ Apr 27, 2015 at 5:59
$\begingroup$
$\endgroup$
If that isn't a typo, you can separate that into 4 recurrences (for starting points 0, 1, 2, 3) by the change of variables $r = \lfloor n / 4 \rfloor$, $k = n \bmod 4$:
$\begin{equation*} t_k(r + 1) = 3 t_k(r) + 4 r + k \qquad t_k(0) = T(k) \text{ for } 0 \le k < 4 \end{equation*}$
They are all first order linear recurrences. Solutions are of the form:
$\begin{align*} t_k(r) &= t_k(0) \cdot 3^r + \frac{r + 2}{2} \cdot 3^r - \frac{4 r + k + 2}{2} \\ &= \Theta(r \cdot 3^r) \\ T(n) &= \Theta(n \cdot 3^{n/4}) \end{align*}$
