Error in the use of asymptotic notation

Question

I'm trying to understand what is wrong with the following proof of the following recurrence

$$ T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n $$ $$ T(n) \leq 2\left(c\left\lfloor\frac{n}{2}\right\rfloor\right)+n \leq cn+n = n(c+1) =O(n) $$

The documentation says it's wrong because of the inductive hypothesis that $$ T(n) \leq cn $$ What Am I missing?

Answer 1

Let's say the final goal is to prove $T(n) = \mathcal{O}(n)$. You start with the induction hypothesis:

$T(i) \leq ci$ for all $i < n$.

And to complete the proof, you have to show that $T(n) \leq cn$ as well.

However, what you're able to deduce is $T(n) \leq (c+1)n$, which is not helpful to complete the proof; you need one constant $c$ for (almost) all $n$. Therefore, we cannot conclude anything and $T(n) = \mathcal{O}(n)$ isn't proved.

Notice that you are confused between the result and the proof process. And one more point, $T(n)$ is actually $\Theta(n \log n)$ in this case so you may consider an appropriate induction hypothesis to be able to prove it.

Answer 2

You've omitted a few steps. It looks like you're attempting to prove by induction that $T(n) = O(n)$, and your proof goes:

Suppose $T(k) = O(k)$ for $k<n$. This means $T(k) \le c \, k$ for some $c$. Then $T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$, so $T(n) = O(n)$.

This proof goes wrong right from the start: “$T(k) = O(k)$ for $k \lt n$” does not make sense. Big oh is an asymptotic notion: $T(k) = O(k)$ means that there is some constant $c$ and a threshold N such that $\forall k \ge N, T(k) \le c \, k$. And again at the end, you can't conclude that “$T(n)=O(n)$”, because that says something about the function $T$ as a whole and you've only proved something about the particular value $T(n)$.

You need to be explicit about what $O$ means. So maybe your proof goes:

Suppose that $T(k) \le c \, k$ for all $k < n$. Then $T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$.

This does not prove an inductive step: you started from $T(k) \le c \, k$, and you proved that for $k=n$, $T(k) \le (c+1) \, k$. This is a weaker bound. Look at what this means: $T(k) \le c \, k$ means that $c$ is a bound for the rate of growth of $T$. But you have a rate $c$ that grows when $k$ grows. That's not a linear growth!

If you look closely, you'll notice that the rate $c$ grows by $1$ whenever $k$ doubles. So, informally, if $m=2^p k$ then $c_m = c_k + p$; in other words, $c_k = c_0 \log_{2} k$.

This can be made precise. Prove by induction that for $k \ge 1$, $T(k) \le c \log_2(k)$.

The recurrence relation is typical for divide-and-conquer algorithms that split the data in two equal parts in linear time. Such algorithms operate in $\Theta(n\,\mathrm{log}(n))$ time (not $O(n)$).

To see what the expected result is, you can check the recurrence relation against the master theorem. The division is $2T(n/2)$ and the extra work done is $n$; $\log_2(2) = 1$ so this is the second case for which the growth is $\Theta(n\,\log(n))$.

Answer 3

I'm extending the answer already given, perhaps only by explaining my comment in more detail.

As guessing can clearly be difficult and tedious, sometimes better methods exist. One such method is the Master Theorem. Our recurrence is now of the form $T(n) = a T(n/b) + f(n)$, where $a \geq 1$ and $b > 1$ are constants and $f(n)$ a function. Note that in our case $\lfloor n/2 \rfloor$ can be interpreted to mean $n/2$. To be technically exact, our recurrence might not be well-defined because $n/2$ might not be an integer. However, this is allowed since it will not affect the asymptotic behaviour of the recurrence. Therefore, we often find it convenient to drop floors and ceilings. The formal proof of this is a bit tedious, but the interested reader can find it for example from the Cormen et al. book.

In our case, we have $a = 2$, $b = 2$, $f(n) = \Theta(n)$. This means that we have $n^{\log_b a} = n^{\log_2 2} = n$. The second case of the Master theorem applies since $f(n) = \Theta (n)$, and we have the solution $T(n) = \Theta (n \log n)$.