3
$\begingroup$

Given the algorithm

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 < 3 \\ T(\frac{n}{2}) + T(\frac{n}{2} + 1) & \text{otherwise} \end{cases} $ which I guessed to be $O(n)$; I've managed to find suitable $c$ and $n_0$, even an extra variable $b$, from which my bound holds but it fails certain base cases.

Here's my attempt:

Prove $T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1) = O(n)$, where $T([0, 3)) = 1$.

Try 1

Assume $0 \leq ck$ for $k < n$, $c > 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} < n$ and $\frac{n}{2} + 1 < n$ for $n > 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 < n$, $c > 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?

$\endgroup$
4
  • $\begingroup$ In try 2, since you have set $n_0=3$, you should not check $T(1)$ since $1\ngeq 3$. $\endgroup$
    – John L.
    May 14 at 15:53
  • $\begingroup$ I thought the upper bound for the base case should always hold. $1$ is within the base case, right? yet $n_0 = 3$ kind of disregard this... does that mean if my $n_0$ skips the base case, I shouldn't verify it at all? $\endgroup$
    – Mampac
    May 14 at 17:20
  • 1
    $\begingroup$ The base case is NOT fixed. You may include $n=1$ in the base case of your proposition. Or you can choose to exclude it. Your purpose is to search for something that is useful and can be proven. Give yourself more freedom. Please see my answer and exercises thereof as well. $\endgroup$
    – John L.
    May 14 at 17:24
  • $\begingroup$ Another problem: You seem to prove something about natural numbers by induction, but then use $n/2$, which need not be an integer. What kind of division does “n/2” in the problem denote? $\endgroup$
    – Carsten S
    May 15 at 10:26

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

Your second idea is good, there is no need to start at $n = 1$:

You already proved that for $n\geqslant 3$, $T(n) \leqslant n - 1$.

You can now say that since $n-1 \leqslant n$ and since $T(1)\leqslant 1$ and $T(2)\leqslant 2$, then for all $n$, $T(n) \leqslant n$.

(You can consider $T(n) \leqslant n +1$ if you want to include $n = 0$).

$\endgroup$
1
  • $\begingroup$ Or just write $T(n)\le\max(1,n-1)$? $\endgroup$ May 15 at 13:33

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.