An example of how to solve a basic recurrence

The time complexity of most recursive algorithms can be represented by a mathematical function called a recurrence. An example of such function is

$latex T(n) = T(\frac{n}{2}) + 1$

As you can see, solving for some n involves solving for $latex \frac{n}{2}$ and so on and so forth. In order to stop from recursing forever, recurrences also usually have a base case, usually a constant. In this case I am going to omit the base case for simplicity.

Solving recurrences involves a sort of backwards induction technique. Step back for a moment and recall the definition of Big-oh:

$latex f(n) = O(g(n)) \mbox{ if and only if } \exists c, n_0 \ni f(n) \leq c g(n), \forall n \geq n_0$

That reads, $latex f(n) = O(g(n))$ if and only if there exists a $latex c$ and $latex n_0$ such that for every $latex n$ greater or equal to than $latex n_0$, $latex f(n)$ is less than or equal to $latex c g(n)$. Our job is to pick a $latex c$ and $latex n_0$ that makes the condition true.

So, the first task is to pick a $latex g(n)$, given the definition of $latex T(n)$ above, we’ll guess that it is of order $latex lg n$. Now as I mentioned earlier, we will be doing induction, but backwards, so first let’s start with the inductive hypothesis:

$latex T(k) \leq clgk, \forall k < n$

There, that should do. Basically if we’re looking at solving this recurrence for $latex n$, we assume it works for every other number thus far. Now we go ahead and prove it for $latex n$.

Since $latex \frac{n}{2} < n$ when $latex n \geq 2$, if set our $latex n_0 \geq 2$, then we can use this inequality in our proof. Notice that I did not set $latex n_0$ equal to 2! If we set our variables, we cannot unset them later on! Thus we simply provide a bound on $latex n_0$ instead.

From the inequality previously discussed, and our inductive hypothesis, we have $latex T(\frac{n}{2}) \leq clg\left(\frac{n}{2}\right)$ , and by our definition of $latex T(n)$, we now have

$latex T(n) \leq clg\left(\frac{n}{2}\right) + 1$

By getting rid of the recursive term, we have already made this recurrence one step easier to solve. Next, from the rules of logarithms, we transform the equation into

$latex T(n) \leq c \left(lg n – lg 2\right) + 1 = c \left(lg n – 1\right) + 1 = clg n – c + 1$

Notice here that if we pick out $latex c$ to be anything greater than or equal to 1, the right hand side will become less than or equal to $latex clgn$, which is exactly what we want. Therefore set $latex c = 1$, and thus

$latex T(n) \leq clgn$

We have concluded the inductive step, and now all that remains is to show it works for the base case. Since our $latex n_0$ is 2, we must show that our choice of $latex c$ and $latex n_0$ hold true for all inputs less than 2, so 1 in this case. However a problem may arise where some base cases may require a larger $latex c$ value in order for the equation to hold true. Therefore we set $latex c’$ to be the maximum of such $latex c$ values, and our previously picked $latex c$, and by the transitive law of $latex \leq$, our final choice for $latex c’$ will hold for all cases.

Therefore we can conclude that $latex T(n) = O(lgn)$, where $latex c = c’$ and $latex n_0 = 2$.

Notice that in the above example I was not as mathematically formal as I could have been. The above solution works, and is a pretty good outline of how to solve a generic recurrence. I hope this helps someone.