---

Asymptotic analysis of simple recursive algorithms

Some of the algorithms and data structures we've looked at so far — and many more than we'll see later this quarter — are best implemented recursively. Since, in this course, we're interested not only in how things work, but also in how well things work, it becomes necessary for us to be able to perform the same kinds of analyses on recursive algorithms that we've done on iterative ones. In some cases, we'll be able to do that without any additional mathematical tools, because sometimes the analysis is quite obvious when you stop and think a bit about how the algorithm works.

As an example, consider the following recursive function for calculating n! (i.e., the factorial of n), given an input n.

int factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

(We're leaving aside, for the time being, whether one would actually want to implement this function recursively in the first place. In C++, the cost of function calls, relative to the total cost of what we're doing, would almost certainly lead us to want to write this as a loop instead; the overhead cost of the function calls will end up being a substantial portion of the overall time spent. Other programming languages present different tradeoffs, so there are some in which a recursive solution would be appropriate or even preferable. Nonetheless, let's proceed with our analysis, as our goal is to learn analytical approaches that we can apply to many situations.)

If you don't read this function carefully, you might be tempted to say, just because of the overall shape of the code, that it runs in Θ(1) time. It has no loops; it's just a simple if statement with a simple integer expression in each. But if you consider what's actually happening here, you'll see that this conclusion can't possibly be right; if we ask for the factorial of 10, it's easy to see that more work will be done than if we ask for the factorial of 5.

With a deeper understanding of what the function does, you'll probably be able to come up with a correct asymptotic result, even without doing any sort of math. Ultimately, to calculate the factorial of n, we'll perform a sequence of multiplications; so how many will there be? Let's consider what happens when n starts out at 5.

factorial(5) = 5 * factorial(4)   ⇒   5 * 24 = 120
factorial(4) = 4 * factorial(3)   ⇒   4 * 6  = 24
factorial(3) = 3 * factorial(2)   ⇒   3 * 2  = 6
factorial(2) = 2 * factorial(1)   ⇒   2 * 1  = 2
factorial(1) = 1 * factorial(0)   ⇒   1 * 1  = 1
factorial(0) = 1

Is it coincidence that it required exactly five multiplications to calculate the factorial of n? Consider the sequence for factorial(3) and for factorial(10) and you'll see that there's a pattern here: Calculating the factorial of n requires n multiplications and a total of n + 1 function calls. There aren't any shortcuts; that's what is always required. The function calls and the multiplications take a constant amount of time — integers in C++ are always the same size — so we would say that this function runs in Θ(n) time.

Unfortunately, while it was fairly straightforward to unravel this algorithm in our minds and see the totality of what it does, not all recursive algorithms lend themselves to this kind of back-of-the-envelope analysis. Sometimes, as we'll see later in this course, we need mathematical tools to help us to get to the bottom of these mysteries.

---

Recurrences

A recurrence maps inputs to an output in a way that's defined recursively. (Some recurrences are mathematical functions, though not all of them are.) Just as recursively-described data structures are quite often best processed by algorithms that are written recursively, recursive algorithms are quite often best described mathematically using recurrences.

Considering our factorial function from above, we could describe its running time using the following recurrence:

T(0) = a
T(n) = b + T(n - 1)

The recurrence T takes one input n, which represents the input that could be passed to factorial. Based on that input, it calculates the time our factorial function would take to calculate its answer. a and b are constants:

• In the case where n = 0, a represents the length of time spent checking whether n is 0 (in the if statement), determining it is, and then returning 1 as a result. On different machines, this will take different amounts of time, but, all things being equal other than the input n, they will be constant, so we'll name that constant a.
• In the case where n > 0, b represents the length of time spent doing everything other than the recursive call: checking whether n is 0, determining it isn't, subtracting 1 from n, multiplying the result of the recursive call by n, and returning the result.

The only part of the function not described by a and b is the time spent in the recursive call to factorial. But that would be determined using the same recurrence: it would be T(n - 1).

Reducing a recurrence to a closed form

The problem with recurrences is that they can be difficult to glance at and quickly see an asymptotic notation that accurately describes them. You can certainly learn some patterns and work them out in your head when you see recurrences that fit those patterns, but, generally, you sometimes need to work them out mathematically. There are a number of techniques that can be used to reduce recurrences to a closed form, but we'll focus on one called repeated substitution, which will work on all of the recurrences we'll see this quarter (though, notably, doesn't always work).

The idea behind repeated substitution is as simple as it sounds: substitute repeatedly. But the goal isn't just to substitute repeatedly forever; the goal is to substitute repeatedly until we see a pattern develop. When we see a pattern develop, we can prove that the pattern really holds in all cases, then use our knowledge of that pattern to remove the recursive term from the recurrence altogether, leaving behind a closed form (i.e., a mathematical function with no recursion in it); if we can do that, we'll quickly be able to determine the corresponding asymptotic notation for it.

Let's use repeated substitution to reduce our recurrence above to a closed form. Starting with T(n), we'll substitute what we know — that T(n) = b + T(n - 1) — a few times and see what develops.

T(n) = b + T(n - 1)
     = b + (b + T(n - 2))      Because T("something") = b + T("something" - 1) for any "something"
     = 2b + T(n - 2)           Some algebraic simplification
     = 2b + (b + T(n - 3))     Second verse, same as the first
     = 3b + T(n - 3)           Eureka!  A pattern is developing...

At this point, we see an interesting pattern emerging. After the j^th substitution, we have:

T(n) = jb + T(n - j)           We believe this might be true for all j = 1, 2, 3, ...

We've seen that it's true for j = 1, 2, and 3. Would it continue being true if we kept substituting? How can we be sure? On the one hand, we might feel pretty confident just by looking at the algebra we're doing, but if we wanted to prove it — or if the algebra left us less convinced — we could use a mathematical technique called proof by induction.

Interlude: Proof by induction

Using a proof by induction on j, we can prove our pattern is the correct one for all j = 1, 2, 3, ..., in two steps:

• Prove that it's true for j = 1. (This is usually called the base case.)
• Prove that if it's true for some j = k, it must also be true for j = k + 1. (This is usually called the inductive step.)

If we know those two things are true, then a very powerful sequence of implications follows:

• We know it's true for j = 1, because our base case was proven.
• Because we know it's true for j = 1, we're sure it's true for j = 2, thanks to the inductive step.
• Because we know it's true for j = 2, we're sure it's true for j = 3, thanks to the inductive step.
• And so on, forever! So we know it's true for all j = 1, 2, 3, ...

The proof by induction here is fairly short.

• Base Case (j = 1): Prove that T(n) = 1b + T(n - 1).
  • This is trivially true, because it's part of the recurrence itself, which states that T(n) = b + T(n - 1).
• Inductive Step: Assume that T(n) = kb + T(n - k), then prove that T(n) = (k + 1)b + T(n - (k + 1)).
  • One substitution and some algebra gets us there:

    T(n) = kb + T(n - k)
         = kb + (b + T(n - k - 1))
         = (k + 1)b + T(n - k - 1)
         = (k + 1)b + T(n - (k + 1))
    

Finishing up with our recurrence

So, we've demonstrated conclusively that, after j substitutions — for any positive integer j — we have:

T(n) = jb + T(n - j)

This leads to an obvious question: So what? Remember our goal here. We want to turn this recurrence into a closed form, a function with no recursion left in it, so it'll be a function whose shape we understand more clearly. If we know that the pattern above is true for all j, then we can let j be anything we'd like, including a convenient choice that takes our T(n - j) term and lets us replace it with something that isn't recursive. We know that T(0) = a. So, if j can be anything we want and it'll still be true, then how about if we let j = n?

T(n) = nb + T(n - n)
     = nb + T(0)
     = nb + a

At first, the function nb + a still looks complicated, but remember that both a and b are constants. Any function of the form nb + a, where both a and b are constants, has a linear growth rate. (As n gets large, a becomes irrelevant; meanwhile, the constant coefficient b doesn't affect the growth rate of the function.)

So, to conclude, we see that T(n) — the time it takes to calculate the factorial of n using our recursive factorial function — is Θ(n).