0
$\begingroup$

Here's the question: Solve the recurrence by obtaining a $\theta$ bound for $T(n)$ given that $T(1) = \theta(1)$.

$T(n) = n + T(n-3).$

Attempted Solution:

\begin{align*} T(n) &= T(n-6) + (n-3) + n \\ &= T(n-9) + (n-6) + (n-3) + n \\ &= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + \cdots + n]\\ &= T(1) + [0 + 3 + 6 + \cdots + n]\\ &= \theta(1) = 3[1 + 2 + 3 + \cdots + n/3]\\ &= \theta(1) + \frac{(n/3)(n/3 + 1)}{2}\\ &= \theta(1) + \frac{n^2+3n}{6}. \end{align*} When I double check to see if the solution fits the recurrence, it doesn't work. I can solve these fairly easily when it involves the previous term, but this $T(n-3)$ is throwing me off. Been at this one for a while now; please help T__T

  • 0
    @Mitch: oh wait...I get it now. The function is assumed everywhere defined but we are only told that it satisfies the recurrence. What you're saying is absolutely right: the function is only underdetermined by neglecting to specify its first three values. Wow...not my finest hour.2011-01-31

3 Answers 3

2

From the initial condition on $T(1)$ and the recurrence relation, there is no way to estimate $T(n)$ unless $n=3k+1$ for some $k\ge0$.

For every $k\ge0$, let $U(k)=T(3k+1)$. Then $U(k)=3k+1+U(k-1)$, hence $U(k)=(3k+1)+(3k-2)+\cdots+4+U(0)$, that is, $T(3k+1)=\frac12k(3k+5)+\Theta(1)$.

1
  • if you have no clue about the general manipulation of the formula, try some specifics. For example, let $T(0)=T(1)=T(2)=0$, then $T(3) =$ ??, $T(6) =$ ??, etc. and then guess a solution.
  • you have no problem with recurrences with T(n-1). One trick with recurrences is to convert the weird inscrutable ones (like for you this $T(n-3)$) -somehow- to $T(n-1)$. The previous bullet point will help with that...create a new function to solve for $S(n)$ where $S(n) = T(3n)$ (you might also have to do it for $T(3n+1)$ and $T(3n+2)$ ). This is called 'change of variables'.

This might seem like more work than it's worth, just to solve this problem, but you've already spent time trying to solve it without getting anywhere so might as well try the extra work.

Actually...you seem to have implicitly done these steps in your attempted solution. Have you checked your steps? What is $n/3(n/3+1)$?

  • 0
    I'm upvoting this because I was going to suggest the change of variables.2011-01-31
0

The reasoning given at StackOverflow works (assuming $n \equiv 1 \pmod 3$) except that there was a slight error in the calculation of the summation $4 + 7 + \ldots + n/3$, which is equal to $(4 + n)(n - 1)/6$ and not $(4 + n)(n - 1)/3$. Letting $m = (n-1)/3$, you can express this summation as follows:

$[\sum_{i = 1}^{m}(3i + 1)]$

= $m + \sum_{i=1}^{m}3i$

= $m + 3 \cdot \sum_{i=1}^{m}i$

= $m + 3[ m \cdot (m + 1)/2]$

= $m + (3m^2 + 3m)/2$

= $(3m^2 + 5m)/2$

= $[3((n-1)/3)^2 + 5((n - 1)/3)]/2$

= $(n^2 - 2n + 1 + 5n - 5)/6$

= $(n^2 + 3n - 4)/6$

= $(n + 4)(n - 1)/6$

= $(n-1)/3 + [(n-1)^2 + 3(n-1)]/6$

= $(5(n-1) + (n-1)^2)/6$

= $(5n - 5 + n^2 - 2n + 1)/6$

= $(n^2 + 3n - 4)/6$

= $(n + 4)(n-1)/6$

...so $T(n) = \Theta(1) + (n+4)(n-1)/6$, as you pointed out on StackOverflow.

  • 0
    @Jason: right, this seems to be some standard sloppiness. What is really meant is $T(n) = O(n) + 2 T( \lceil \frac{n}{2} \rceil)$.2011-02-06