10
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Recurrences of this form can also be solved using the Master theorem. $\endgroup$ – Juho Mar 25 '12 at 21:36
  • 2
    $\begingroup$ @Ran: I don't think master-theorem is an appropriate tag for this question. The question is not about how to solve it , but to point out the fallacy in a particular argument. Besides, master-theorem is probably too specific, and probably does not deserve to have its own tag. In general, we should be tagging based on the question, not possible answers. For instance, would you tag this akra-bazzi? $\endgroup$ – Aryabhata Mar 26 '12 at 3:35
  • $\begingroup$ "what is wrong with the following proof" -- I don't see a proof. It is often helpful to write down a complete proof (i.e. make the induction explicit) in order to spot mistakes. $\endgroup$ – Raphael Mar 26 '12 at 6:49
  • $\begingroup$ A related more general question is Solving or approximating recurrence relations for sequences of numbers. $\endgroup$ – Juho Jul 27 '12 at 20:11
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ if we replace c'=c+1 , will it make any change? $\endgroup$ – Erb Mar 26 '12 at 14:13
  • $\begingroup$ @erb: No, it won't. You have to prove for a chosen constant. If replacing $c'=c+1$, you eventually have $T(n) \leq (c'+1)n$ (or $T(n) \leq (c+2)n$) then the outcome is the same. $\endgroup$ – pad Mar 26 '12 at 15:42
8
$\begingroup$

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))$.

$\endgroup$
7
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Thanks! It may be noted that "dropping floors and ceils" corresponds to assuming that $n=2^k$ which is commonly done. The basic observation is that for non-decreasing functions, the asymptotic growth of subsequences equals the asymptotic growth of the whole sequence. $\endgroup$ – Raphael Mar 26 '12 at 9:58

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.