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.
It’s fate. 60-100 to study for, and a post a recent topic?
Too bad I’m not really studying :/