1
$\begingroup$

I'm a self-taught and I'm studying from CLRS. I'm having difficulty with this recurrence relation: $$T(n)=3T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + n$$

The problem is that I can "prove" that $T(n) = \mathcal{O}(n)$. It's absurd. My inductive hypothesis about $\mathcal{O}(n)$ is: $$\exists c \gt 0 \,\,\exists n_0 \gt 0 \,\,\exists b \ge 0 \quad\forall n_0\le k\lt n \quad T(k) \le ck - bn \le ck $$

From here I haven't problem during the "proof": $$\begin{align} T(n) &\le 3\left(c\left\lfloor{\frac{n}{2}}\right\rfloor - bn\right) + n \\ &\le 3\left(c\frac{n}{2} - bn\right) + n \\ &= \frac{3}{2}cn - 3bn + n \\ &= \frac{3}{2}cn -n(3b - 1) \qquad\qquad (1st) \\ &\le cn \end{align}$$

The latter holds $\forall b \ge \frac{c+2}{6}$ and it comes from: $$\frac{3}{2}cn - n(3b - 1) \le cn$$


--EDIT--
It's also easy to prove that $$(1st) \le cn - bn$$ It holds $\forall b \ge \frac{c+2}{4}$
So $$T(n) \le cn - bn$$ --END EDIT--


So I think that the hypotheses are wrong. Probably I misunderstanding subtraction of lower-order term. What are the constraints to apply this technique? Only that $T(k) \gt 0$? In this recurrence the latter seems valid.

Synthesis: https://cs.stackexchange.com/questions/65549/lower-order-term-constraints-and-wrong-guess/65579?noredirect=1#comment139380_65579

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Nov 4 '16 at 13:34
  • $\begingroup$ I suggest you try very clearly writing out your base case and inductive hypothesis, including what things are existentially quantified and what are universally quantified. your proof attempt seems to consist mostly of a sequence of statements with no explicit connection between them. $\endgroup$ – David Richerby Nov 4 '16 at 13:46
  • $\begingroup$ @DavidRicherby Thank you for your reply. I appreciate it. I edited it in proper way. However in these case the base case is necessary? T(b), where T(b) represents base case, is costant. So you can always find a good costant for asymptotic inequality. So the proof of inductive step is sufficient. Furthermore the base case it's not indicated on the book. $\endgroup$ – Druner John Nov 4 '16 at 15:59
  • $\begingroup$ I do not understand your inductive hypothesis for proving $O(n)$. What is $b$? $\endgroup$ – aelguindy Nov 4 '16 at 17:03
  • $\begingroup$ @aelguindy Thank you for your reply. It's a constant that I added to subtract lower-order term, I find this way very flexible. $\endgroup$ – Druner John Nov 4 '16 at 17:39
2
$\begingroup$

First of all, the way you state the induction hypothesis is a bit strange, and it definitely doesn't prove that $T(n) = O(n)$. Assuming that the induction is on $n$, what your induction hypothesis states (more or less) is that for every $n$ there exists $C$ such that $T(k) \leq Ck$ for all $k \leq n$. The function $T(n) = n^2$ satisfies this, with $C = n$.

What you really want to do is to fix the parameters $b,c,n_0$ in advance. In other words, you want to prove $$ \exists b,c,n_0 \, \forall n \, \forall n_0 \leq k \leq n\colon T(k) \leq ck - bn. $$ You first instantiate $b,c,n_0$, and then you prove only the following part by induction: $$ \forall n \, \forall n_0 \leq k \leq n\colon T(k) \leq ck - bn. $$ At each step of the induction, you are proving $$ \forall n_0 \leq k \leq n\colon T(k) \leq ck - bn $$ for the current value of $n$.

Now for your mistake. Your induction hypothesis states that for all $k \leq n$, $$ T(k) \leq ck - bn. $$ However, in the inductive step, you only prove $$ T(k) \leq ck. $$ Also, you only prove it for $k = n$, despite the form of your actual induction hypothesis.

Indeed, it is very strange that your inductive hypothesis gives an upper bound on $T(k)$ which depends on $n$. This is quite unorthodox. Usually the upper bound only depends on $k$. Moreover, you are not really subtracting a lower-order term: $n \neq o(k)$!

Here is what an application of subtracting a lower-order term usually looks like. Suppose that we want to prove that $T(n) = O(n)$. Then you find $b,c,n_0$ and prove the following by induction:

$$ \forall n \geq n_0\colon T(n) \leq bn - c\log n.$$

Note that there is no $k$ here, and that $\log n = o(n)$ is indeed of lower order.

Improve this answer
$\endgroup$
16
  • $\begingroup$ Thank you for your reply. First: do I have to find the three constants? Second: as I suspected my hypothesis is buggy. I didn't want to say that for every n there exist a constant C, but there exists a constant C for all n etc.. Then I stated $T(k) \le ck - bn \le ck$. So if I prove $T(n) \le cn$ why is not valid? However there isn't difficulty to "prove" that $T(n) \le ck - bn$. I've difficulty.. $\endgroup$ – Druner John Nov 5 '16 at 8:59
  • $\begingroup$ You need to prove that the constants exist. They don't have to be explicit. $\endgroup$ – Yuval Filmus Nov 5 '16 at 9:00
  • $\begingroup$ Your main error is that you assume one thing and prove another. You assume $T(k) \le ck - bn$ but prove $T(k) \le ck$. Induction requires you to assume and prove the same property. $\endgroup$ – Yuval Filmus Nov 5 '16 at 9:02
  • $\begingroup$ Do you mean by induction? As I say it's easy to "prove" that $T(n) \le cn - bn$. $\endgroup$ – Druner John Nov 5 '16 at 9:05
  • $\begingroup$ I think that my primary problem is that I can't identify hypothesis and thesis. In this case my thesis to $T(n)=O(n)$ is $\forall n \ge n_0 : T(n) \le cn$ isn't that true? I've to prove the latter by induction with this hypothesis: $\exists c,n_0 \forall n_0 \le k \lt n :T(k) \le ck$, isn't that true? $\endgroup$ – Druner John Nov 5 '16 at 9: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.