debugMinor
Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
Viewed 0 times
caseboundthesubstitutionmethodfailsusingforfindupper
Problem
Given the algorithm
I defined a recurrence
$ T(n) = \begin{cases}
1 & 0 \leq n 0$, must show $T(n) \leq cn$, $\forall n \geq n_0$.
$T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1)$, since $\frac{n}{2} 2 \implies n_0 > 2 \implies T(\frac{n}{2}) \leq \frac{cn}{2}$ and $T(\frac{n}{2} + 1) \leq \frac{cn}{2} + c \implies$
$T(n) \leq \frac{cn}{2} + \frac{cn}{2} + c = cn + c$
$\overset{?}{\leq} cn$ is not possible since $c > 0$.
Try 2
Assume $0 \leq ck - b$ for $k 0$, $b > 0$ must show $T(n) \leq cn - b$, $\forall n \geq n_0$.
$T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1)$
$\leq \frac{cn}{2} - b + \frac{cn}{2} + c - b = cn - b - b + c = cn - b - (b - c)$
$\leq cn - b$, as long as $b - c \geq 0$
$\implies b \geq c$. From here, it's not clear how to find $b$ and $c$. Strangely, this expression is also independent of $n$.
If we take $c = b = 1$, $n_0 = 3$ then the $T(3) = T(1.5) + T(2.5) = 2 \leq 3 - 1 = 2$ bound holds, but the base case, for example, $T(1) = 1 \leq 1 - 1$ fails.
Is there any way of making this work?
MYSTERY-ALG(n >= 0)
1 if n < 3 then
2 return 1
3 else
4 return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1)I defined a recurrence
$ T(n) = \begin{cases}
1 & 0 \leq n 0$, must show $T(n) \leq cn$, $\forall n \geq n_0$.
$T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1)$, since $\frac{n}{2} 2 \implies n_0 > 2 \implies T(\frac{n}{2}) \leq \frac{cn}{2}$ and $T(\frac{n}{2} + 1) \leq \frac{cn}{2} + c \implies$
$T(n) \leq \frac{cn}{2} + \frac{cn}{2} + c = cn + c$
$\overset{?}{\leq} cn$ is not possible since $c > 0$.
Try 2
Assume $0 \leq ck - b$ for $k 0$, $b > 0$ must show $T(n) \leq cn - b$, $\forall n \geq n_0$.
$T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1)$
$\leq \frac{cn}{2} - b + \frac{cn}{2} + c - b = cn - b - b + c = cn - b - (b - c)$
$\leq cn - b$, as long as $b - c \geq 0$
$\implies b \geq c$. From here, it's not clear how to find $b$ and $c$. Strangely, this expression is also independent of $n$.
If we take $c = b = 1$, $n_0 = 3$ then the $T(3) = T(1.5) + T(2.5) = 2 \leq 3 - 1 = 2$ bound holds, but the base case, for example, $T(1) = 1 \leq 1 - 1$ fails.
Is there any way of making this work?
Solution
The problem in the question is a good example for two related principles.
-
Thanks to the substitution method in your try 2, you have found $c=b=1$ will enable the induction step for $T(n)\le cn-b$ to work. However, if the base case is $T(1)$, the inequality does not hold.
Instead of sticking to proving "$T(n)\le n-1$ for $n\ge0$", you can try proving "$T(n)\le n-1$ for $n\ge 3$" instead. Now the base case is "$T(n)\le n-1$ for $3\le n\lt 6$", which can be proved easily.
When we want to find some proposition that can be proven by mathematical induction, we can change the domain of the proposition so that the base case in a mathematical induction will be able to succeed. This useful freedom of choice can enable us to make progress. (We could also, of course, change the proposition so that the base case can succeed.)
-
If we can prove $T(n)\le n-1$ for $n\ge n_0$ from some $n_0$, it means $T(n)\le n$ for $n\ge n_0$, i.e., $T(n)=O(n)$. It does not matter whether $n_0=1$, or $n_0=3$, or $n_0=2022$.
The big-$O$ notation is about asymptotic behavior. The behavior when $n$ is small can be ignored.
Two easy exercises
Exercise 1: Show by mathematical induction that $T(n)\le n-1$ for $n\ge3$, considering the base case as when $3\le n\lt 6$.
Exercise 2: Show by mathematical induction that
$T(n)\begin{cases}=1,\quad\quad\text{ if }0\le n\lt 3\\\le n-1,\text{ otherwise} \end{cases}$, considering the base case as when $0\le n\lt 3$. This is another way to change the base case.
-
Thanks to the substitution method in your try 2, you have found $c=b=1$ will enable the induction step for $T(n)\le cn-b$ to work. However, if the base case is $T(1)$, the inequality does not hold.
Instead of sticking to proving "$T(n)\le n-1$ for $n\ge0$", you can try proving "$T(n)\le n-1$ for $n\ge 3$" instead. Now the base case is "$T(n)\le n-1$ for $3\le n\lt 6$", which can be proved easily.
When we want to find some proposition that can be proven by mathematical induction, we can change the domain of the proposition so that the base case in a mathematical induction will be able to succeed. This useful freedom of choice can enable us to make progress. (We could also, of course, change the proposition so that the base case can succeed.)
-
If we can prove $T(n)\le n-1$ for $n\ge n_0$ from some $n_0$, it means $T(n)\le n$ for $n\ge n_0$, i.e., $T(n)=O(n)$. It does not matter whether $n_0=1$, or $n_0=3$, or $n_0=2022$.
The big-$O$ notation is about asymptotic behavior. The behavior when $n$ is small can be ignored.
Two easy exercises
Exercise 1: Show by mathematical induction that $T(n)\le n-1$ for $n\ge3$, considering the base case as when $3\le n\lt 6$.
Exercise 2: Show by mathematical induction that
$T(n)\begin{cases}=1,\quad\quad\text{ if }0\le n\lt 3\\\le n-1,\text{ otherwise} \end{cases}$, considering the base case as when $0\le n\lt 3$. This is another way to change the base case.
Context
StackExchange Computer Science Q#151558, answer score: 4
Revisions (0)
No revisions yet.