1
$\begingroup$

What exactly are we doing from a CS perspective when we solve a recurrence relation and find a resulting formula for a sequence given a set of initial conditions? I just went through the "linear homogeneous recurrence relations of degree k with constant coefficients" bit in discrete math and basically understand the math part and have a simple process for solving them mechanically.

What I haven't seen yet is an explanation of what this correlates to in a CS sense. I understand we will encounter recurrence relations in algorithms which we haven't reached yet (next class) but I'm wondering what exactly do the initial conditions and the sequence represent?

For a trivial programming example, if we were to write a recursive function to process a directory and all its subdirectories, I understand conceptually that could be modeled as a recurrence relation because it is recursive, but I don't know how, and I don't know what the initial conditions and final formula for the sequence would represent in such a scenario.

Here's an example of the type of relation I'm talking about. So we solve these by taking the relation down into its characteristic equation, finding the roots, and then building a system of equations from the initial conditions $a_0, ..., a_j$ that we solve to find the constants. Finding the constants gives a closed formula for that particular sequence defined by those initial conditions.

My question is, from a CS/programming/software engineering perspective what would we model using recurrence relations like this other than algorithms, and what would the initial conditions represent in those models?

$\endgroup$
  • $\begingroup$ "which we haven't reached yet (next class)" -- a little impatient, are we? :) $\endgroup$ – Raphael Jun 26 '16 at 0:48
  • $\begingroup$ @Raphael just a bit. :) I've waited 20 years to finish this degree. Math is much harder now unfortunately. $\endgroup$ – Dave Jun 26 '16 at 1:25
4
$\begingroup$

In computer science, recurrence relations are often useful for analyzing the running time of algorithms. For instance, we might define a function $T(\cdot)$, so that $T(n)$ is the running time when running the algorithm on an input of size $n$. Often, for many kinds of algorithms, we can write a recurrence relation that expresses $T(n)$ in terms of smaller values, such as

$$T(n) = 2T(n/2) + O(n).$$

This would be saying that the running time to solve a problem of size $n$, is twice the time to solve a problem of half that size (perhaps because we recursively solve the first half and the second half using the same algorithm), plus $O(n)$ more (perhaps to combine/merge their two solutions).

So, the numbers represent running times -- the number of operations the algorithm takes to solve the problem. You might like to take a look at Reference answers to frequently asked questions and How to come up with the runtime of algorithms?. Also take a look at algorithms textbooks, especially their chapters on running time analysis and divide-and-conquer algorithms.

The initial condition of a recurrence (e.g., the value of $T(1)$) depicts the running time of the algorithm on a small instance. Often, for a recursive algorithm, this is the running time of the base case.

In computer science, the sequence we are considering is

$$T(1),T(2),T(3),T(4),T(5),\dots,$$

i.e., the sequence of running times as the input size increases. If you were to write down the sequence of running times for some algorithm, you might spot a pattern, where each term can be computed by a simple formula of a few previous terms (namely, the pattern indicated by the recurrence relation). That said, honestly, thinking about this as a sequence might not be the most helpful or intuitive viewpoint (at least, I don't find it to be so); I find it more intuitive to think of $T(\cdot)$ as a function rather than a sequence. The same mathematics still applies.

Another way to get some intuition is to work through a few examples where recurrences are used to analyze the running time of some simple algorithms. I think that will also help you get a better intuition of what the mathematical expressions mean and how they relate to the algorithm.

$\endgroup$
  • $\begingroup$ Thanks for taking the time to comment. I get that they represent the running time of algorithms. What I'm looking for is what the initial condition of a recurrence relation would represent "in the real world", and what the output sequence of that recurrence relation would likewise represent. In other words, I can solve a basic recurrence relation if you give me one with initial conditions, but as a long-time programmer going through CS I don't see how to relate the abstract number calculations back to something I've actually done. Hope that makes sense. $\endgroup$ – Dave Jun 24 '16 at 20:25
  • $\begingroup$ @Dave, I'm afraid I don't know what you mean by "output sequence", so I don't know how to address that. Can you edit the question to explain more about what you're looking for? As far as initial conditions, see my edited answer. (Tip for the future: it helps if you make sure to describe in the question what you're looking for, in the initial version, so we don't have to go through a few iterations to understand what aspects you're hoping to have explained.) $\endgroup$ – D.W. Jun 24 '16 at 22:41
  • $\begingroup$ I just edited my question to clean it up a bit. After reading a bit more it turns out I had a slight misunderstanding which led to my use of the term "output sequence" -- we are not generating a new sequence from the closed form solution, just deriving the closed form for the initial defined sequence. My apologies for that mistake. Thanks for your edits, that makes it a bit more clear. I'm not great at math but I'm fascinated by modeling, and want to learn more, so I'm looking for ways to tie what I'm learning back to real-world problems. Hope that makes sense. $\endgroup$ – Dave Jun 25 '16 at 4:11
  • $\begingroup$ @Dave, OK, makes sense! Good edit. I edited my answer once more to try to address that point. $\endgroup$ – D.W. Jun 25 '16 at 5:19
2
$\begingroup$

The following is an answer to your first question “What exactly are we doing from a CS perspective when we solve a recurrence relation and find a resulting formula for a sequence given a set of initial conditions?”

Two motivations or reasons for finding a corresponding formula for a given recurrence relation and set of initial condition are to reduce the amount of memory and the time needed to compute the solution or the answer.

An “easy” (in terms of human effort) way to find the solution to a recurrence relation would be to use a recursive function: run it and hope for two things to happen – not to encounter a stack overflow and get an answer soon. This is “easy” for a human being because he or she does three basic things: translates the recurrence relation into a recursive function, run the recursive function, and wait for a response from the computer. It becomes a “challenge” if he or she cannot wait any longer for a response or the recursive function takes too long to find the answer or if the recursive function runs into a stack overflow – in other words, out of memory error. It is very tempting to use a recursive function because it is easy to translate a recurrence relation to a recursive function, and it works for “small problems” in a learning environment.

$\endgroup$
  • $\begingroup$ Excellent thank you for this answer. I've written recursive functions in production code before but the problems have always been bound at least implicitly. In effect we were restricting the input domains. Ex: recursively processing a directory and assuming we won't crash, just like you said. My understanding here is that we are searching for general algorithms that we can prove will run in a known finite time for a relatively arbitrary input. So we can determine mathematically before we code whether or not we are wasting time. Is that correct? $\endgroup$ – Dave Jun 28 '16 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.