Asymptotics are a way for us compare the growth of two functions. This sounds kind of strange—why not just compare the outputs? But rather than figuring out whether a function is always less than some other function, we are really more interested in how the function grows as input grows larger. To do this, we have to turn an idea from calculus/analysis: asymptotic analysis.
This is used in analysis of algorithms. Typically, we count the number of "steps" that are taken by an algorithm as a function of the size of the input. But there are issues with this approach: the number of operations can depend on implementation quirks, like programming choices or even the particular architecture of the machine. We avoid this by performing our analysis asymptotically rather than exactly. This way, we are able to abstract away many of the small, unimportant details of implementation and get a better idea of whether the broader strategy of the algorithm is efficient.
Here is the formal definition for the idea we would like to work with.
Let $f:\mathbb N \to \mathbb R$ be a function. We say that $f(n)$ is $O(g(n))$ for some function $g:\mathbb N \to \mathbb R$ if there exist constants $c \gt 0$ and $n_0 \geq 0$ such that for all $n \geq n_0$, $|f(n)| \leq c \cdot |g(n)|$.
We call this "big O" notation. Roughly speaking, big O gives us an upper bound on the growth of a function. This system of notation is due the German analytic number theorists Bachmann and Landau in the late 19th Century and is sometimes called Landau notation. Its use in the analysis of algorithms was popularized by Donald Knuth in the 1960s.
We should note that we are primarily interested in functions with positive inputs and outputs, which is why we're considering the magnitude of the functions in our definitions. And so, we can get away with dropping them. Let's see an example.
We claim that $f(n) = n^2 + 100n + 1$ is $O(n^2)$. Note that when $n \gt 1$, we have \[0 \leq n^2 + 100n + 1 \leq n^2 +100n^2 +n^2 = 102n^2.\] So we can take $c = 102$ and $n_0 = 1$ as our constants to show that $f(n)$ is $O(n^2)$.
In fact, we can make the coefficient of $n$ as large as we like, and we would still be able to show that $f(n)$ is $O(n^2)$. The math checks out: we're always able to choose a large enough constant that we can get over the initial 'hump', since the growth of the $n^2$ term eventually outpaces the $n$ term. This highlights the basic idea behind asymptotic analysis being about orders of growth.
Note that a common thing to do when using big O notation is to write something like $f(n) = O(g(n))$. This is not strictly correct, since these two things aren't really equal. For instance, writing $O(g(n)) = f(n)$ looks strange, because $O(g(n))$ isn't a function! One can argue that it's really a class of functions, and we could write something like $f(n) \in O(g(n))$. But in the end, we put up with this notational abuse because it is too late.
Now, note that without any additional properties, we would have to go through a proof based on the definition in order to do any comparisons, like we did above. However, there are a number of properties and identities that are quite easy to prove that will make our lives considerably easier and that allow for the kind of loosey-goosey way we typically introduce big O notation to first-time computer science students.
Let $f:\mathbb N \to \mathbb R$ be a function.
We'll prove (3). We let $c_1$ and $n_1$ be the constants that show $f_1(n)$ is $O(g_1(n))$ (that is, $f_1(n) \leq c_1 \cdot g_1(n)$ for all $n \geq n_1$) and $c_2, n_2$ be the constants that show $f_2(n)$ is $O(g_2(n))$. We will show that for $f(n) = f_1(n) + f_2(n)$, we have $n_0 = \max(n_1,n_2)$ and $c = c_1 + c_2$ such that $f(n)$ is $O(\max(g_1(n),g_2(n)))$. Then we have for $n \geq n_0$, \begin{align*} f_1(n) + f_2(n) &\leq c_1 \cdot g_1(n) + c_2 \cdot g_2(n) \\ &\leq c_1 \cdot \max(g_1(n),g_2(n)) + c_2 \cdot \max(g_1(n),g_2(n)) \\ &\leq (c_1 + c_2) \cdot \max(g_1(n),g_2(n)) \\ &\leq c \cdot \max(g_1(n),g_2(n)) \end{align*}
For the most part, big O notation works almost how we would expect it to, particularly with polynomial functions. However, if we're not careful, we can get into some tricky situations.
Exponents are one place where one has to be pretty careful. Consider $f(n) = 4^n$. One might be tempted to say that $4^n$ is $O(2^n)$ since 4 is larger than 2 by a constant. If it were, then we would have constants $n_0$ and $c$ such that $4^n \leq c \cdot 2^n$ for all $n \geq n_0$. Since both sides are positive for all $n$, we can divide both sides by $2^n$. This gives us \[\frac{4^n}{2^n} = \frac{2^{2n}}{2^n} = 2^n \leq c\] for all $n \geq n_0$. But this inequality cannot hold for any choice of $c$ and $n_0$.
Here is another shortcut that can cause some issues. We often think of constants as $O(1)$, so we write things like $4 = O(1)$. This is because if $f(n) = 4$, then $f(n)$ is indeed $O(1)$. Now, consider the following argument: \begin{align*} f(n) &= \sum_{i = 0}^n i \\ &= 1 + 2 + \cdots + n \\ &= O(1) + \cdots O(1) \\ &= O(n). \end{align*} What's the error here? We weren't careful: we're considering functions of $n$ and $i$ is not constant. In fact, $f(n)$ is $O(n^2)$, since $f(n) = \frac{n(n+1)}2$.
There are also corresponding notions for the lower bound ("big omega") and asymptotically tight bounds ("big theta").
Let $f:\mathbb N \to \mathbb R$ be a function. We say that $f(n)$ is $\Omega(g(n))$ for some function $g:\mathbb N \to \mathbb R$ if there exist constants $c \gt 0$ and $n_0 \geq 0$ such that for all $n \geq n_0$, $|f(n)| \geq c \cdot |g(n)|$.
Let $f:\mathbb N \to \mathbb R$ be a function. We say that $f(n)$ is $\Theta(g(n))$ for some function $g:\mathbb N \to \mathbb R$ if there exist constants $c_1,c_2 \gt 0$ and $n_0 \geq 0$ such that for all $n \geq n_0$, $c_1 \cdot |g(n)| \leq |f(n)| \leq c_2 \cdot |g(n)|$.
We will leave these for now. Here are some useful things to know. You can try to prove them using the results from above.
Let $f: \mathbb N \to \mathbb R$ be a function.
We'll show (2), that $\log_a n$ is $\Theta(\log_b n)$ for all bases $a,b \gt 1$. In effect, the base of the logarithm doesn't really matter (as long as it's greater than 1). This fact is pretty much second nature to theoreticians and it often drives students insane when I say that something is logarithmic without specifying the base. Here is the reason why.
Recall that $\log_a n = \frac{\log n}{\log a}$. Then \[\log_a n = \frac{\log n}{\log a} = \frac{\log b}{\log a} \cdot \frac{\log n}{\log b} = \frac{\log b}{\log a} \cdot \log_b n.\] Note that $\frac{\log b}{\log a}$ is a constant. This means that by taking $n_0 = 0$ and $c_1, c_2 = \frac{\log b}{\log a}$, we have \[\frac{\log b}{\log a} \cdot \log_b n \leq \log_a n \leq \frac{\log b}{\log a} \cdot \log_b n\] for all $n \geq 0$, and therefore $\log_a n$ is $\Theta(\log_b n)$.
One of the things that makes analysis of algorithms and similar kinds of counting problems tricky is when we are confronted with a recursive procedure. In this case, counting the number of steps of an algorithm or other similar objects requires describing the term of a function based on the function itself applied to previous terms. These are called recurrence relations and we will touch upon a few ways to deal with them.
There are a few classic examples where recurrences arise. The first of these is the Tower of Hanoi, where there are a stack of discs of increasing size that you have to move between three pegs, you being one of several Tibetan monks/Hindu priests, depending on which telling of the story we're dealing with. You want to move the stack of discs to another peg with the condition that the order of the stack is preserved. Furthermore, you can only move one disc to another peg at a time and you can't place a larger disc on top of a smaller disc. Upon the placement of the final disc to complete the task, the world will end.
Suppose we have $n$ discs (we have generalized the problem but the monks/priests only have to deal with 64 discs). How many times do we have to move a disc in order to move the entire stack to another peg?
To count this, let's think recursively. Let $H_n$ denote the number of moves required to move the top $n$ discs from one peg onto another. In order to move the final, largest disc, we need to have moved the stack of $n-1$ discs onto another peg, so this is $H_{n-1}$ moves. Then, we move the largest disc onto the remaining open peg. Once we have done this, we move the $n-1$ discs so that they go on top of the largest disc, which is another $H_{n-1}$ moves. In total, we have made $H_n = 2H_{n-1} + 1$ moves to move $n$ discs.
Now, we've developed a recurrence relation, but we want a closed form for it. This leads us to the first technique to solving recurrences: try some stuff and hope it works and if it does, use induction to cook up a formal proof. This is not too different from when we had to guess the closed form of a sum back when we were discussing induction. This involves looking at the first few terms and trying to divine something out of the sequence we get. First, we set the initial conditions by observing that $H_0 = 0$ and $H_1 = 1$. Then we have \begin{align*} H_0 &= 0 \\ H_1 &= 1 \\ H_2 &= 3 \\ H_3 &= 7 \\ H_4 &= 15 \\ H_5 &= 31 \\ H_6 &= 63 \\ \end{align*}
Here, we notice this looks suspiciously like $2^n - 1$, so we can test this hypothesis by substituting this into the formula: $$H_n = 2H_{n-1} + 1 = 2 \cdot (2^{n-1} - 1) + 1 = 2^n - 2 + 1 = 2^n - 1.$$ This appears to work, so if we want to go ahead and prove this formally, we have all the pieces to construct a proof by induction. This is called the substitution method.
But what if we're faced with a sequence that we may not readily recognize? We can try an alternative approach that is pretty much the same as guessing, but from the other direction: expand the first few iterations of the recurrence. If we do this to our Tower of Hanoi recurrence, we get the following: \begin{align*} H_n &= 2H_{n-1} + 1 \\ &= 2(2H_{n-2} + 1) + 1 \\ &= 2^2 H_{n-2} + 2 + 1 \\ &= 2^3 H_{n-3} + 2^2 + 2 + 1 \\ &= 2^4 H_{n-4} + 2^3 + 2^2 + 2 + 1 \\ &= 2^5 H_{n-5} + 2^4 + 2^3 + 2^2 + 2 + 1 \end{align*} and so on. Again, this involves hoping that you will be able to see some sort of pattern emerge, and if you have a keen eye, you can deduce that the last few terms of this expansion will look like \begin{align*} H_n &= 2H_{n-1} + 1 \\ &= 2(2H_{n-2} + 1) + 1 \\ & \vdots \\ &= 2^{n-1} H_1 + 2^{n-2} + \cdots + 2^2 + 2 + 1 \\ &= 2^{n-1} + 2^{n-2} + \cdots + 2^2 + 2 + 1 \\ &= 2^n - 1 \end{align*} at which point, you can test your hypothesis further or cook up an inductive proof to prove this formally. This is called the iteration method.
And how long do the monks/priests have to go at this for before the end of the world approaches? The story assumes one move of a disc to take one second, giving us $$H_{64} = 2^{64} - 1 = 18446744073709551615$$ seconds to complete the movement of 64 discs. That's about 585 billion years, which is about 42 times the age of the universe, 130 times the age of the sun, and about as much of Unix time we can keep track of with an unsigned 64-bit integer.
In algorithms analysis, the form of recurrence we tend to see is the following.
A divide-and-conquer recurrence is a recurrence of the form \[T(n) = a T\left(\frac n b\right) + f(n)\] where $a$ is the number of subproblems, $b$ is the factor by which we decrease the size of the subproblem, and $f(n)$ is the cost of combining solutions to subproblems.
What does this mean? Let's look at an example.
Recall that the binary search algorithm works as follows:
How many steps does this take? Let's count the number of comparisons that are performed as a proxy of the number of steps. We notice that we only ever perform one comparison per iteration of our algorithm. If we proceed to the next iteration, we decrease the size of our list by half. We can express this by the following recurrence: \[T(n) = T\left(\frac n 2\right) + 1.\]
Here's a more complicated example.
Suppose we want to find both the maximum and the minimum of a list of numbers in an unsorted list. We can do this by splitting the list in half and finding the maximum and minimum in the two smaller lists. Then we just need to do two comparisons: which maximum is bigger and which minimum is smaller? This gives us the following recurrence for the number of comparisons performed: \[T(n) = 2T\left(\frac n 2\right) + 2.\]
We can take this idea a bit further.
Suppose we want now want to sort a list. Again, we can do this by splitting the list in half and sorting the two smaller lists. Then we just need to do a bunch of comparisons to put the list back together. Since the elements are mostly in order, we just need to perform one comparison for each element. This gives us the following recurrence for the number of comparisons performed: \[T(n) = 2T\left(\frac n 2\right) + n.\]
So this occurs often enough that we probably want to know if there's a more systematic way to solve this kind of recurrence? We can gain some intuition about how to work with this by looking at its associated recursion tree. For convenience, we assume that $n$ is a power of $b$. Then at each level, each problem breaks into $a$ subproblems.
What this means is that on the $i$th level of the tree, we have a total of $a^i$ subproblems, each of size $\frac{n}{b^i}$. In total, we will have $1 + \log_b n$ levels. Now, suppose also that we have $f(n) = n^c$ for some fixed constant $c$ (please ignore the fact that the illustration says $k$). Here, $f(n)$ is the amount of work that we need to do to combine the results of our work on the subproblems. We have the following.
Adding all of these up, we have \[T(n) = \sum_{i=0}^{\log_b n} a^i \left( \frac{n}{b^i} \right)^c = n^c \sum_{i=0}^{\log_b n} \left(\frac{a}{b^c}\right)^i.\]
We would like to know what the asymptotic behaviour of this recurrence is. This will depend on what $a,b,c$ are, which will determine which factor of $T(n)$ dominates.
Taking $r = \frac{a}{b^c}$ and $k = \log_b n$ together with the fact that $\frac{a}{b^c} \lt 1$ if and only if $c \gt \log_b a$, we arrive at the following.
Let $a \geq 1, b \geq 2, c \gt 0$ and let $T:\mathbb N \to \mathbb R^+$ be defined by \[T(n) = aT\left(\frac n b\right) + \Theta(n^c), \] with $T(0) = 0$ and $T(1) = \Theta(1)$. Then, \[ T(n) = \begin{cases} \Theta(n^{\log_b a}) & \text{if $c \lt \log_b a$}, \\ \Theta(n^c \log n) & \text{if $c = \log_b a$}, \\ \Theta(n^c) & \text{if $c \gt \log_b a$}. \\ \end{cases} \]
This is called the Master Theorem in the famed algorithms textbook, Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, because it magically solves many of the recurrences we tend to see in algorithms and because most instructors don't really get into the proof. Observe that I skillfully avoided many details. But the origins of this particular recurrence and its solutions is due to Bentley, Haken, and Saxe in 1980, partly intended for use in algorithms classes.
Recall our recurrences from above:
Each of these is solvable as follows:
We will be looking at a different kind of recurrence for which we know the form of the solution.
Let's think about a problem similar to the kind that I've been throwing at you: How many binary strings of length $n$ do not contain $00$ as a substring?
We could attempt to use one of our previous counting techniques to solve this one, but recall that strings are also recursively defined structures. It is helpful to count such strings in terms of how they're extended. In other words, we can consider the number of strings of length $n$ that don't contain $00$ in terms of the number of such strings of length $n-1$. This is because every string of length $n$ is a string of length $n-1$, but with an additional $0$ or $1$.
Let $A_n$ be the set of strings of length $n$ that avoid $00$ and let $a_n = |A_n|$. If $w = x1 \in A_n$, then $x \in A_{n-1}$. However, if $w = x0 \in A_n$, then $x$ itself cannot end in $0$. Therefore $x = y1$ where $y \in A_{n-2}$ and so $w = x10$. Putting these together, we find that $a_n = a_{n-1} + a_{n-2}$ for $n \geq 3$. Furthermore, we've seen this recurrence already: it's the same form as the Fibonacci sequence, although with different starting conditions. This leaves $n = 1,2$, which are easy to solve by enumeration.
As promised, we'll tackle how to solve these in just a bit. What we should note is that we are lucky and the recurrence is in one of the forms that allows us to apply a theorem to mechanically solve it, rather than have to guess and hope for the best.
A linear homogenous recurrence of degree $k$ with constant coefficients is of the form $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k},$$ where $c_i \in \mathbb R$ for $1 \leq i \leq k$ and $c_k \neq 0$.
So the Fibonacci recurrence ($f_n = f_{n-1} + f_{n-2}$) is linear and homogenous and has constant coefficients, but the Tower of Hanoi recurrence $(H_n = 2H_{n-1} + 1)$ is not homogenous, because of the constant term. Similarly, a recurrence like $a_n = a_{n-1}^2 + a_{n-2}$ would not be linear and a reccurrence like $a_n = a_{n-1} + n a_{n-2}$ does not have constant coefficients.
Unsurprisingly, these simple looking recurrences appear frequently in mathematics. Conveniently for us, the solution to these recurrences is of a very specific form. First, we'll need the following idea.
The characteristic equation for the linear homogenous recurrence of degree $k$ with constant coefficients $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$ is $$x^k - c_1 x^{k-1} - c_2 x^{k-2} - \cdots - c_{k-1} x - c_k = 0.$$
What we'll see is that the the solution of our linear homogenous recurrences are based on the roots of their characteristic equations.
Suppose that the characteristic equation for a linear homogenous recurrence of degree $k$ has distinct real roots $r_1, r_2, \dots, r_k$. Then the solutions to the recurrence take the form $a_n = b_1 r_1^n + b_2 r_2^n + \cdots + b_k r_k^n$ for real constants $b_1, \dots, b_k$.
There is a proof of this in Rosen for $k = 2$ which is too long to cover in class. However, we can walk through the solution to gain some insight into the connection between linear recurrences and the roots of their characteristic equation.
Consider the recurrence $a_n = 7a_{n-1} - 12a_{n-2}$, with $a_0 = 3, a_1 = 10$.
Without the knowledge of the theorem that tells us the exact form of the recurrence, we would be forced to divine some sort of pattern from the first few terms of the recurrence. What we would observe is something roughly exponential, so we would guess something of the form $r^k$. Plugging this into our recurrence, we get \begin{align*} r^n &= 7r^{n-1} - 12r^{n-2} \\ r^n - 7r^{n-1} + 12r^{n-2} &= 0 \\ r^{n-2}(r^2 - 7r + 12) &= 0 \\ r^{n-2}(r-3)(r-4) &= 0 \end{align*} Here, we begin to see where our solution might have come from. It's not hard to see how linear recurrences like this will have exponential solutions of some sort. The rest is just working out the details: what is the exact form of the solution that will give us the right pattern with the correct initial conditions? Guessing got us on the right track, since we know our solution could involve $3^n$ and $4^n$.
Now, let's apply the theorem. The characteristic equation for $a_n = 7a_{n-1} - 12a_{n-2}$ is indeed $x^2 - 7x + 12 = 0$, just as we had guessed, and it has roots $x = 3,4$. This means that our solution is a linear combination of the two exponential terms $a3^n + b4^n$. To solve for $a$ and $b$, we use our initial conditions $a_0 = 3, a_1 = 10$ to set up the equations \begin{align*} a3^0 + b4^0 &= 3 \\ a3^1 + b4^1 &= 10 \\ \end{align*} Some easy algebra gives us $a = 2, b = 1$. Therefore, the solution to our linear recurrence is $$a_n = 2 \cdot 3^n + 4^n.$$
As promised, we can finally derive the closed form for the Fibonacci numbers. Recall that the Fibonacci numbers are described by the recurrence $f_n = f_{n-1} + f_{n-2}$, which is a linear homogenous recurrence of degree 2. The characteristic equation of this recurrence is $x^2 - x - 1 = 0$. This equation has roots $$\varphi = \frac{1 + \sqrt 5}{2} \text{ and } \widetilde \varphi = \frac{1 - \sqrt 5}{2}.$$ Then we know that the recurrence has solutions of the form $$a \left( \frac{1+\sqrt 5}{2} \right)^n + b \left( \frac{1-\sqrt 5}{2} \right)^n$$ and we need to consider the initial conditions to solve this. So we have \begin{align*} a \left( \frac{1+\sqrt 5}{2} \right)^0 + b \left( \frac{1-\sqrt 5}{2} \right)^0 &= 0 \\ a \left( \frac{1+\sqrt 5}{2} \right)^1 + b \left( \frac{1-\sqrt 5}{2} \right)^1 &= 1 \end{align*} which gives us $a = \frac{1}{\sqrt 5}$ and $b = - \frac{1}{\sqrt 5}$. Thus, $$f_n = \frac 1 {\sqrt 5} \left( \frac{1+\sqrt 5}{2} \right)^n - \frac 1 {\sqrt 5} \left( \frac{1-\sqrt 5}{2} \right)^n = \frac{\varphi^n - \widetilde \varphi^n}{\sqrt 5}.$$ This is Binet's formula, which we saw several weeks ago.
There is one complication that we haven't covered yet. What happens if we have a characteristic polynomial that has multiples of the same root? It doesn't really make sense to have a solution with two terms $r^n + r^n$. The big question is how to separate these two terms. In short, the answer is to separate terms by a factor of $n^i$. In other words, for $k$ repeated roots, we have terms of the form $n^0 r^n = r^n, nr^n, n^2 r^n, \dots, n^{k-1} r^n$. This is more formally stated in the following theorem.
Suppose that the characteristic equation for a linear homogenous recurrence has distinct real roots $r_1, \dots, r_t$ with multiplicities $m_1, \dots, m_t$ respectively such that $m_i \geq 1$ and $m_1 + \cdots + m_t = k$. Then the solutions to the recurrence take the form $$a_n = \sum_{i = 1}^t \sum_{j = 0}^{m_i - 1} n^j b_{i,j} r_i^n$$ for real constants $b_{i,j}$ with $1 \leq i \leq t$ and $1 \leq j \leq m_i$.
Consider the recurrence $a_n = 6a_{n-1} - 9a_{n-2}$ with $a_0 = 2, a_1 = 3$. This recurrence has a characteristic equation $x^2 - 6x + 9 = 0$, and therefore has a root 3 of multiplicity 2. This means that our solution will be of the form $a3^n + bn3^n$. As usual, we solve for $a$ and $b$ using the initial conditions, \begin{align*} a3^0 + b \cdot 0 \cdot 3^0 &= a = 2 \\ a3^1 + b \cdot 1 \cdot 3^1 &= 3a + 3b = 3 \end{align*} This gives us $a = 2$ and $b = -1$ and so the solution to the recurrence is $$a_n = 2 \cdot 3^n - n 3^n = (2-n)3^n.$$
There is one more curveball that we can throw that is not too hard to deal with. This is when we are confronted with a nonhomogenous recurrence. We've already seen an example of such a recurrence, the Tower of Hanoi recurrence $H_n = 2H_{n-1} + 1$.
A linear nonhomogenous recurrence relation with constant coefficients is a recurrence relation of the form $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots c_k a_{n-k} + F(n),$$ where $c_1, \dots, c_k$ are real numbers and $F(n)$ is a nonzero function that depends only on $n$. The recurrence $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots c_k a_{n-k}$$ is called the associated homogenous recurrence relation.
The very convenient thing about recurrences of this form is that part of the solution is formed by the associated homogenous recurrence, and so, we can make use of our work from before. The only complication is how to deal with the nonhomogenous term.
Let $a_n = c_1 a_{n-1} + \cdots c_k a_{n-k} + F(n)$ be a recurrence relation, where $c_1, \dots, c_k$ are real numbers and $F(n)$ is a nonzero function. If $\{g_n\}$ is a particular solution to the recurrence $a_n$ and $\{h_n\}$ is a solution to the associated homogenous linear recurrence, then all solutions of $a_n$ are of the form $\{g_n + h_n\}$.
Consider two solutions to $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} + F(n)$, say $f$ and $g$. That is, we have \begin{align*} f_n &= c_1 f_{n-1} + c_2 f_{n-2} + \cdots c_k f_{n-k} + F(n), \\ g_n &= c_1 g_{n-1} + c_2 g_{n-2} + \cdots c_k g_{n-k} + F(n). \end{align*} Then it is clear that $f-g = h$ is a solution to the associated homogenous linear recurrence of $a_n$ and we have $f = g + h$.
Consider the recurrence $a_n = 3a_{n-1} + 2n$ with $a_0 = 2$. We know how to solve the associated homogenous recurrence, $a_n = 3a_{n-1}$, easily; we have $h_n = a3^n$ for some constant $a \in \mathbb R$.
Now, we need to find a possible solution. For now, we will guess such a solution, observing that $F(n) = 2n$, and guessing that a linear function $g_n = bn+c$ may work. Substituting this into the recurrence gives us $$bn+c = 3(b(n-1) + c) + 2n.$$ We can then rearrange this to $(2b+2)n + 2c-3b = 0$ and solve for $b$ and $c$ by \begin{align*} 2b+2 &= 0 \\ 2c-3b &= 0 \end{align*} This gives us $b = -1$ and $c = -\frac 3 2$, and we have $g_n = -n - \frac 3 2$. Then by Theorem 22.14, all solutions of our recurrence are of the form $$a_n = g_n + h_n = -n -\frac 3 2 + a 3^n.$$ To complete this solution, we just need to consider our initial condition $a_0 = 2$. This gives us \begin{align*} a_0 &= a3^0 - 0 -\frac 3 2 \\ 2 &= a - \frac 3 2 \\ a &= \frac 7 2 \end{align*} Thus, our solution is $a_n = \frac 7 2 \cdot 3^n - n - \frac 3 2$.
Of course, we would like some certainty in our lives and guessing is a bit too shaky for most of us to feel comfortable with. Surely, there's a better way? It turns out that if $F(n)$ is of a particular form, then there is.
Let $a_n = c_1 a_{n-1} + \cdots c_k a_{n-k} + F(n)$ be a recurrence relation, where $c_1, \dots, c_k$ are real numbers and $F(n)$ is a nonzero function. Suppose $F(n)$ is of the form $$F(n) = (b_t n^t + \cdots + b_1 n + b_0)s^n,$$ where $b_0, \dots, b_t$ are real numbers and $s$ is a constant.
The distinction between the two cases at the end have to do with whether we can just tack on a term with $s^n$ to our solution. If the characteristic equation doesn't have a root $s$, then we can just add it. If $s$ is a root, then we have to multiply it by a term $n^m$ to ensure that it's separate, in the same way that we would have had to with multiples of the same root.
But what if $F(n)$ isn't of this form? Well, then we're out of luck, which is just as well, because we've reached the end of this course.
We've seen a number of different kinds of recurrences, each performing a slightly different kind of recursive process:
Observe how the different approaches lead to very different algorithmic costs. The first two, perform recursive operations on subproblems whose sizes decrease by 1 but do not perform very much work at each level, if any. But the divide and conquer recurrence models a process that performs much more work at each iteration but with much smaller subproblems. The first two are exponential in cost, while the last is polylogarithmic. This leads to some interesting conclusions about the nature of recursive algorithms and how to think about solving problems recursively.
Of course, this is something that you will learn more about in Algorithms.