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

  • 2
    already answered here: http://stackoverflow.com/questions/4839849/recurrence-relation-homework-struggles2011-01-29
  • 0
    This seems to be written in the language of computer science rather than mathematics. Can someone explain to me what a $\theta$ bound is, and what $T(1) = \theta(1)$ means here?2011-01-29
  • 0
    Also, to my eye the problem is ill-posed, since the recurrence does not define $T$ for all $n$.2011-01-29
  • 0
    @Pete: Yes, this notation is common in computer science (but historically, it derives from notation created for number theory). Also, yes, not all base cases are defined. The culture for HW problems like this is to really assume constant values for any missing base cases.2011-01-29
  • 0
    @Mitch: okay, but what does it *mean*? Also, filling in any finite number of values is not going to be sufficient: the recursion still won't define a function on all positive integers.2011-01-30
  • 0
    To make my question more clear: according to wikipedia, in computer science the "big theta" symbol is used to mean the same thing I would mean by $f \asymp g$ -- i.e., $f$ is bounded above and by below by a constant times $g$. In this context $T(1) = \Theta(1)$ would mean "$T(1)$ is bounded". But $T(1)$ is a single value, so of course it's bounded: there's no information being conveyed here. So I must be missing something...2011-01-30
  • 0
    @Pete: Yes, $\Theta(n)$ is as you say. It 'means' that the base case is a constant, not growing (not a function of $n$). When one asks 'solve this recurrence', it is not to find a function (well, of course sometimes there's enough information to do that) but to bound the function (which is what is usually cared about in computer science). So if $T(1)$ is bounded above and below by a constant times ... 1, then it is... well not exactly...but might as well be a constant if all you want to do is bound the function $T(n)$.2011-01-30
  • 0
    @Pete: I'm fairly certain that $T(1) = \Theta(1)$ is an informal way of telling us that the time of the base operations is independent of the inputs. For example, if we want to sort an array of integers, our main operations will be how many comparisons and swaps we need to make. To say that $T(1) = \Theta(1)$ tells us that the time it takes to compare numbers $m$ and $n$ and the time it takes to swap objects at indices $i$ and $j$ are both bounded by constant functions.2011-01-30
  • 0
    @Jason: Where are the "base operations" here? I don't see an algorithm or anything like that: all I see is an (imperfectly) recursively defined sequence. Is this really a common way of writing CS homework problems? It seems incredibly sloppy.2011-01-30
  • 0
    @Pete: The algorithm is usually mentioned in the context of the recurrence relation so the base operations are often implicit, but yes, from what I've seen, this is very common. Unfortunately, I wouldn't be surprised if your point were not addressed in cs courses, especially at the intro level.2011-01-30
  • 0
    @Pete L. Clark - T(n) is the number of operations to solve a particular problem of size n. Both are positive integers, and the problem, probably, only exists in sizes of 3*k+1. Indeed the domain is integers 1 mod 3. Also, in this case, theta(1) implies that T(1) is a constant. The problem is to find a closed form function. Sorry to say, but its very common CS. I hope the question makes more sense now.2011-01-30
  • 0
    Oh, and 'why not just make the obvious change of variable', I guess that's exactly the answer OP is looking for :)2011-01-30
  • 0
    @Pete:"Why couldn't we have $T(3n+2)=2^{2^n}$ for all $n$, for instance?". This may seem petty, but it couldn't be because it wouldn't satisfy the recurrence. You are right, $T(n)$ is underdetermined as a total function, but the point of the exercise is to determine bounds (which the Big-Oh and Theta notation allows us to do). The fact that two base cases are missing is definitely annoying, but fixable. "How do we bound a function without knowing how it's defined every where?": without going into the details, it's the machinery of Theta notation that allows you to do that.2011-01-31
  • 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
    The $3$ dropped out for some reason so it should be $3 \cdot [n/3(n/3 + 1)/2]$ resulting in the same final solution presented.2011-01-31
  • 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
    Why are you assuming $n \equiv 1 \pmod 3$?2011-01-31
  • 0
    @Pete: This was so I justified the case mentioned in the answer on StackOverflow where the answerer says the sum becomes "$T(1) + [4 + 7 + \ldots + n]$", but the final solution I gave to the recurrence relation can be verified to work for all $n \in \mathbb{N}$ by considering the other two congruences.2011-01-31
  • 0
    @Pete: the assumption for $1 \bmod 3 $ is because of the missing two other base cases.2011-01-31
  • 0
    @Mitch: I thought we had established that all three base cases are missing but that one need not know their values to answer the question. Whatever $T(1) = \Theta(1)$ is supposed to mean, it is *not* specifying the value of $T$ at $1$, right?2011-01-31
  • 0
    @Pete: Sorry for reintroducing doubt. The only base case like thing in the original question is $T(1) = \Theta(1)$, it does not mention $T(2)$ or $T(3)$. Since the recurrence goes back 3, these two are needed for $T(3k+2)$ and $T(3k)$. To read between the lines, equivalently to specify this appropriately for TCS culture, the question should state either the two extra base cases or say instead $T(\Theta(1)) = \Theta(1)$, meaning -all- base cases are constants (which of course, they must be anyway, or you'd be talking about a family of functions). Which is to say...2011-01-31
  • 0
    @Pete: ...which is to say, in the idiom of TCS, yes, it -is- specifying a value at $T(1)$, you just don't know what it is other than that it is bounded. It might make you feel better just to say that $T(1) = c_1$, some unspecified constant.2011-01-31
  • 0
    @Pete: Perhaps $T(1)$ can (also) serve as a way of specifying the desired precision so in this case it would mean that the function should be determined up to the addition of an unspecified constant. Specifically, we want a function satisfying this recurrence relation for all $n \in \mathbb{N}$, but depending on the congruence of $n \pmod 3$, the constant that we'll be adding will be different (unless $T(2)$ and $T(3)$ were very specific values). If $T(1)$ were some precise value, then we might be inclined to have an exact function for each of the $3$ cases.2011-01-31
  • 0
    @Pete: You should also consider the recurrence relation for quicksort in the best case (i.e., $T(n) = O(n) + 2T(n/2)$). Now we only have a recurrence relation defined down to $T(1)$ for powers of $2$.2011-01-31
  • 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