2
$\begingroup$

In CLRS, it works through an example going through a recurrence relation proof using the "substitution method".

We have the recurrence $$T(n) = 2T(\lfloor n/2 \rfloor) + n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.19)$$

It claims:

We guess that our solution is $T(n) = O(n \lg(n)).$

We assume that $T(m) \leq cm\lg(m)$ for all $m < n$ (in particular, for $m = \lfloor(n/2) \rfloor$, and need to show that $T(m) \implies T(n).$

I'm fine with this; this seems like a standard case of strong induction, but what I don't understand is the explanation of the base case (which we also need to prove):

enter image description here

Could someone explain this paragraph to me? More specifically:

  • What are boundary conditions?
  • How do we know the base case? We're only given $T(n)$ recursively; there's no initial case when $n$ is, for example, $1$. How, then, do we know that "$T(1) = 1$"?
  • I don't understand what the paragraph is getting at. How do we determine the base case in the general case?

Also, I've noticed that, in practice examples, the author has failed to mention the base case completely when doing these types of proof; that is, they assume the inductive hypothesis, and prove that (for all $m<n$), $T(m) \leq \text{something} \implies T(n) \leq \text{something}$, but they leave it at that, as though that were sufficient for the proof. In fact, these proofs don't even explicitly state the inductive hypothesis. For example, in the case of (4.19), they would write something like: $$ \begin{align} T(n) \leq c\lfloor( n/2) \rfloor \lg(\lfloor n/2\rfloor) \end{align} \\ \leq \ ... \\ \leq cn\lg(n) \ .$$

Is this acceptable, or would that constitute a sloppy proof?

$\endgroup$
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Jul 17 '17 at 20:15
1
$\begingroup$

What are boundary conditions?

The boundary condition here refers to the base case(s) of the induction. This makes more sense in an intuitive manner if we consider, for instance, a 2D case: Suppose $T(m,n)$ is the running time of an algorithm where the input parameters are $m$ & $n$ are non-negative integers. Now, assume we have a recurrence relation of the form, say, $T(m,n) = T(m-1,n)+T(m,n-1)$

Arguably, the boundary condition that needs to be supplied for an inductive proof of $T(m,n)$ would be $T(m,0)\ \forall\ m \geq 0 $ & $T(0,n)\ \forall\ n \geq 0$. Thus, the set of $ (m,0),\ m \geq 0$ along with $ (0,n),\ m \geq 0$ can be thought of as a boundary(identifiable with the first quadrant axes). Thus, coming back to the question at hand, the boundary conditions are nothing but the specification of the values of the recurrence at the edge of its applicable domain. This in 1D turns out to be point(s) at the end of the interval.

How do we know the base case? We're only given T(n) recursively; there's no initial case when n is, for example, 1. How, then, do we know that "T(1)=1"?

When setting up a recurrence relation, it is always a good practice to specify the domain of applicability of the relation. This as we just saw above can help identify the boundary of validity of the relation. Now, the next step of how we come to know the exact values taken by the function at the boundary is often a problem of understanding the algorithm for which we have setup the recurrence relation for. In this particular case of $T(1) = 1$, we obtain $T(1)$ by manually computing(using the algorithm) the (worst-case)time it will take to work on an input of size 1.

How do we determine the base case in the general case?

This is where the understanding of the algorithm(and its correctness) becomes crucial. Knowing the boundary of domain of the recurrence relation and the approximations we want to use to bound the range of the recurrence on a given size of input determines the cases for which we will need to supply the starting terms of the recurrence relation.

For instance, even though the natural boundary point for the example in your question is the input of size 1, due to the approximation being used namely $cnlg(n)$, we need to perturb the boundary in order to get a new domain such that the approximation will work on all possible inputs for the new domain of the recurrence. This is why the input $1$ is discarded and the boundary(in 1D it usually a single point if the interval is finite in a direction) and a new boundary point, $n_0 = 2$ is chosen.

Also, I've noticed that, in practice examples, the author has failed to mention the base case completely when doing these types of proof;...In fact, these proofs don't even explicitly state the inductive hypothesis...Is this acceptable or sloppy proof?

You are correct in stating that a base case as well as explicit verification using the inductive hypothesis is needed for the proof of induction to be complete and valid. However, in most treatments of this nature, when the base case/inductive hypothesis is not explicitly invoked, it is usually a passive call to action on the reader that they have been supplied with enough information to figure that out for themselves.

$\endgroup$
  • $\begingroup$ Thanks for the detailed answer. Just a few things: 1) When I asked "How do we determine the base case in the general case", the base case to which I was referring was the base case of the recurrence itself, not of the inductive hypothesis. I'm still a little uneasy accepting that T(1) = 1 in this particular case. Normally, recurrences explicitly define initial/boundary conditions. When it is not specified, can we just assume that the initial condition is always T(1) = 1? $\endgroup$ – Spongebob Jul 19 '17 at 21:12
  • $\begingroup$ 2) What happens if the minimum $n_0$ for which the inductive hypothesis holds, is a big number (e.g. 10,000)? Is there any quick way of determining such a number, without recursively computing $T(2), T(3), \cdots , T(10,000)$ and then seeing if our desired inequality holds for each of these values of $n_0$? $\endgroup$ – Spongebob Jul 19 '17 at 21:12
  • $\begingroup$ 3) Is the induction that is being used here "strong induction" or "normal induction"? We're assuming that $T(m) \leq \cdots $ for all $m<n$, and we show that $T(m) \leq \cdots \implies T(n) \leq \cdots $ for all $n$, but we haven't used the fact that $T(m) \leq \cdots $ **for all** $\ m$; we've only used that it's true for a particular value of $m$. Does that mean we're using "normal induction"? $\endgroup$ – Spongebob Jul 19 '17 at 21:23
  • $\begingroup$ Thanks for the feedback, Let me try to respond to your points. 3) You are correct, we don't use the fact that $T(m)$ is true for all $m < n$. We however, need that it is true for value of $\lfloor n/2 \rfloor$ specifying which integer this is differs based on whether n is odd or even. In order to not worry about this issue, we assume stronger induction since then we can assume hypothesis is true for $\lfloor n/2 \rfloor$ without worrying about exactly which integer this i going to be in relation to n being odd or even... $\endgroup$ – LastIronStar Jul 20 '17 at 4:53
  • $\begingroup$ ... 2) I'm afraid there's no way around this but to manually calculate for the worst case on the input of size 10,000(by your example). That being said, this kind of large base case for the recursion is unlikely to be encountered in practice. $\endgroup$ – LastIronStar Jul 20 '17 at 4:56
1
$\begingroup$

What are boundary conditions?

Given a recurrence/function $f$ boundary conditions are simply a few points, usually small points such as 0,1 or 2, at which $f$ is specified. For example, in the Fibonacci sequence $$F(n) = F(n-1) + F(n-2), F(0) = F(1) = 1$$ $F(0),F(1)$ are boundary conditions. In other words initial conditions, base conditions.

The excerpt you posted proves the upper bound for the recurrence relation $2T(\lfloor n/2 \rfloor) + n$. It is done using substitution method for solving recurrence relation where you first guess the solution (involving constant(s)) and then find constant(s) that would satisfy boundary conditions.

After you guessed the solution you get an explicit (as in your example) equality/inequality of the form $T(n) \leq cg(n)$ which you have to prove in order to establish the upper bound for the recurrence relation $T(n)$. That is usually done using induction. However, the original boundary conditions may fail when you use it with your guessed function $g(n)$ like in the example: $T(1) = 1$, but $c\log(1) = 0$. At this point you should kind of select new boundary conditions (initial points) to prove the inequality $T(n) \leq cg(n)$. Without base step you cannot complete induction proof.

So the example "overcomes this obstacle" by choosing a new value $n_0$ for the inductive proof. However, $T(1) = 1$ is still kept but it is removed from the inductive proof. The example then introduces new boundary conditions $T(2)$ and $T(3)$ instead of $T(1)$. Given $T(1)= 1$, we have $T(2)= 4$ and $T(3)=5$ and so for some constant $c \geq 2$ the following conditions hold $T(2) \leq c2\log(2)$, $T(3) \leq c3\log(3)$.

Now you can prove that $T(n) < cn\log(n)$ using induction by taking base step $n=2$ and $n=3$ ($n \geq 2$).

How do we know the base case?

If base case (boundary conditions) of the original recurrence relation fails, you can just remove them from the new equation/inequality and introduce new base case for which the equation/inequality holds.

I don't understand what the paragraph is getting at.

This paragraph is just one simple example demonstrating how a new substitution function fails at the original boundary conditions and how to overcome that problem.

How do we determine the base case in the general case?

There is no a standard way to do that, use you intuition, guess, and check if it works. You should choose your boundary conditions carefully. In the example you in your post $T(2)$ and $T(3)$ are chosen as new boundary conditions since values of $T(2)$ and $T(3)$ directly depend on the value of $T(1)$ which is troublesome. So we just put $T(2)=4$ and $T(3)=5$ without using $T(1)$.

Making a good guess

Unfortunately, there is no general way to guess the correct solutions to recurrences. Guessing a solution takes experience and, occasionally, creativity. Fortunately, though, you can use some heuristics to help you become a good guesser.


Is this acceptable, or would that constitute a sloppy proof?

This inequality should be proven. Assume that our claim is true for all integers less than or equal to $n$. We need to show that the inequality is true for $n+1$.

$$ T(n+1) = 2T((n+1)/2) + (n+1) \leq 2c\frac{n+1}{2}\lg{\frac{n+1}{2}} + (n+1) = c(n+1)\lg{\frac{n+1}{2}} + (n+1)=(n+1)(c\lg{\frac{n+1}{2}} + 1) \leq (n+1)(c\lg{\frac{n+1}{2}} + c) = c(n+1)(\lg{\frac{n+1}{2}} + 1) = c(n+1)(\lg{\frac{n+1}{2}} + \lg2) = c(n+1)\lg{(n+1)}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.