1

I only saw one problem involving induction so I am not sure what to do here. Here is what I tried and where I got stuck:

For $n=1$, $T(1)=1\leq 1*1$, so we are covered.

The hypothesis would be that for all $k<n$, $T(k)=O(k)$. From here I believe that we could say that for all $n$ larger than some $n_0$:

$T(⌊\frac{n}{2}⌋)\leq c*⌊\frac{n}{2}⌋$ and $T(⌈\frac{n}{2}⌉)\leq c*⌈\frac{n}{2}⌉$

I believe that I am supposed to choose the same $c$ for both of them, but not completely sure.

Now this is where I get stuck:

$T(n)=T(⌊\frac{n}{2}⌋)+T(⌈\frac{n}{2}⌉)+1\leq c*⌊\frac{n}{2}⌋+c*⌈\frac{n}{2}⌉+1=c*n+1$

When I was taught this method it was stressed that it is important to prove the case for $T(n)$ for the same $c$ from the hypothesis however it does not seem possible to me here.

How can I proceed?

איתן לוי
  • 839
  • 4
  • 9

1 Answers1

1

Sometimes it's helpful to determine an appropriate value for $c$ to use. You're given that $T(1) = 1$ and

$$T(n) = T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + T\left(\left\lceil\frac{n}{2}\right\rceil\right) + 1 \tag{1}\label{eq1A}$$

Trying the next few values, you get

$$T(2) = T(1) + T(1) + 1 = 1 + 1 + 1 = 3 \tag{2}\label{eq2A}$$

$$T(3) = T(1) + T(2) + 1 = 1 + 3 + 1 = 5 \tag{3}\label{eq3A}$$

$$T(4) = T(2) + T(2) + 1 = 3 + 3 + 1 = 7 \tag{4}\label{eq4A}$$

$$T(5) = T(2) + T(3) + 1 = 3 + 5 + 1 = 9 \tag{5}\label{eq5A}$$

As you can see, you get $T(n) = 2n - 1$, which you can prove fairly easily by induction. However, to instead directly prove that $T(n) = O(n)$ by induction, you can use $c = 2$ and prove $T(n) \lt cn = 2n$ (although the technical definition is for $\le$, you can use just $\lt$ as that's more strict and, thus, included in $\le$). The base case is true, i.e., $T(1) = 1 \lt 2(1)$. Next, use strong induction to assume it's true for all $n \le k$ for some $k \ge 1$. Note since $T(n) \lt 2n$ for all $1 \le n \le k$, this means that $T(n) \le 2n - 1$ since it's values are all integral. Thus, using that $\left\lfloor\frac{k+1}{2}\right\rfloor \le k$ and $\left\lceil\frac{k+1}{2}\right\rceil \le k$, plus that $\left\lfloor\frac{k+1}{2}\right\rfloor + \left\lceil\frac{k+1}{2}\right\rceil = k + 1$ for all integers $k$, you have

$$\begin{equation}\begin{aligned} T(k + 1) & = T\left(\left\lfloor\frac{k+1}{2}\right\rfloor\right) + T\left(\left\lceil\frac{k+1}{2}\right\rceil\right) + 1 \\ & \le \left(2\left\lfloor\frac{k+1}{2}\right\rfloor - 1\right) + \left(2\left\lceil\frac{k+1}{2}\right\rceil - 1\right) + 1 \\ & = 2\left(\left\lfloor\frac{k+1}{2}\right\rfloor + \left\lceil\frac{k+1}{2}\right\rceil\right) - 1 \\ & = 2(k + 1) - 1 \\ & \lt 2(k + 1) \end{aligned}\end{equation}\tag{6}\label{eq6A}$$

This shows the inductive step also holds, confirming that $T(n) \lt 2n$ for all $n \ge 1$, meaning that $T(n) = O(n)$. Note since $T(n) \lt 2n$, it's also trivially true that $T(n) \le 2n$, meaning the definition of $O$ holds for any $c \ge 2$, i.e., you have $T(n) \le cn$.

John Omielan
  • 47,976
  • I am required to use the formal definition, using $<$ instead of $\leq$ is not allowed. – איתן לוי Nov 09 '19 at 23:48
  • If $T(n)<2n$ then trivially $T(n)\leqslant 2n$ as well... – Math1000 Nov 09 '19 at 23:51
  • Of course, but $\leq$ does not mean $<$, which by the formal definition is the only thing you can assume. – איתן לוי Nov 09 '19 at 23:53
  • @איתןלוי As Math1000 stated, if something is $\lt$, then it also $\le$. I added an extra sentence to the end of my answer stating this. – John Omielan Nov 09 '19 at 23:59
  • @JohnOmielan This is not what I am saying. What I am saying is that by the definition, when you assume $T(k)=O(k)$ you may only use the fact that $T(k)\leq ck$, you don't know that $T(k)<ck$ because it is MORE information that what the definition gives you. – איתן לוי Nov 10 '19 at 00:03
  • @איתןלוי The question only asks you to prove that $T(n) = O(n)$, i.e., there's a $c$ such that $T(n) \le cn$, by induction, i.e., this is the final result. It doesn't say you need to use this in any part of the inductive proof before the conclusion, i.e., in particular, in the inductive step, i.e., that $T(k) = O(k)$. Forgetting about $O$ for now, if I wanted to prove $Q \le R$, if I can prove that $Q \lt R$, I've accomplished this since $Q \le R$ trivially holds as $\le$ means $\lt$ or $=$. Sometimes, in proofs, it's easier to prove a somewhat more stringent requirement than necessary. – John Omielan Nov 10 '19 at 00:16