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