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

As you can see, solving for some n involves solving for 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:

That reads, if and only if there exists a and such that for every greater or equal to than , is less than or equal to . Our job is to pick a and that makes the condition true.

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

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

Since when , if set our , then we can use this inequality in our proof. Notice that I did not set equal to 2! If we set our variables, we cannot unset them later on! Thus we simply provide a bound on instead.

From the inequality previously discussed, and our inductive hypothesis, we have  , and by our definition of , we now have

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

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

We have concluded the inductive step, and now all that remains is to show it works for the base case. Since our is 2, we must show that our choice of and 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 value in order for the equation to hold true. Therefore we set to be the maximum of such values, and our previously picked , and by the transitive law of , our final choice for will hold for all cases.

Therefore we can conclude that , where and .

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.