I have a recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$. The guess is that it is that $T(n) = O(n^2)$. The book then solves it like below for some constants $c > 0$ and $d > 0$
$$ T(n) \leq 3d \lfloor n/4 \rfloor ^2 + cn^2 $$ $$\leq 3d (n/4)^2 + cn^2$$ $$ = \frac{3/16} dn^2 + cn^2$$ $$ \leq dn^2$$
I have two questions:
- Why do we switch between $\leq$ and $=$ and then back to $\leq$?
- My prof said we won't break the inequality if $d\geq (16/13)c$ because $(3/16) d + c \leq d$, but I don't understand why it shouldn't be $(3/16) d + c \geq d$. If we have some number $ y \leq a + b$ and if we replace $b$ with another constant $x > 0$. Shouldn't we want $x > b$ to maintain the inequality of $\leq$. If $x < b$ that could break the inequality?
Q1) In a "tower" of (in)equalities like here, the relation sign ($\le$, $=$, or whatever is used) is only meant to confer the relation between the last term and the next term. That makes it possible for a reader to see what kind of justification is likely used for that step.
For example the step
$$ 3d \lfloor n/4 \rfloor ^2 + cn^2 \le 3d (n/4)^2 + cn^2 $$
is an inequality, so the reader will look for a change between the sides and see that $\lfloor n/4 \rfloor$ has been replaced with (n/4), which is an inequality ($\lfloor n/4 \rfloor \le n/4$) and then with some more simple arguments will convince themselves that it is true.
OTOH, the step
$$3d (n/4)^2 + cn^2 = \frac{3/16} dn^2 + cn^2$$
is an equality, so the reader will look for substitutions (none here) or rearrangements of terms, and that is what happened and the reader will find there is an error (from your misunderstanding of how "\frac" works in MathJax) and it should be
$$3d (n/4)^2 + cn^2 = \frac{3}{16} dn^2 + cn^2.$$
If you framed the above as inequality, it wouldn't be incorrect but it would be misleading. The reader might look for some kind of inequality used, and will not find it. By using the $=$ relation here, you make the statement easier to verify in praxis. And remember that the reader is likely to be you as well, after some time looking at the solution and trying to see if you made errors.
Note that the last inequality (with above corrected term) is
$$\frac{3}{16} dn^2 + cn^2 \le dn^2,$$
and this is an "I want that to be true" inequality. Your aim is to make that true (by clever choices of $d$), but at the moment you don't know if (or how) this is possible.
Q2) This plays into the last thing I wrote for Q1. Assume in your case you have say $c=1$. Then for example $d=0.1$ would satisfy $(3/16)d+c \ge d$. This means, if we unravel the tower of inequalities, you have proved (assuming that the inequality holds for $\lfloor n/4\rfloor $) that
$$T(n) \le \frac{3}{16} dn^2 + cn^2 = \frac{0.3}{16} n^2 + n^2 =1.01875n^2.$$
Unfortunately, what you need at this moment is
$$T(n) \le 0.1n^2,$$
which you can't get this way!
More generally, what you want is
$$T(n) \le dn^2,$$
what you can prove is
$$T(n) \le \frac{3}{16} dn^2 + cn^2 = (\frac{3}{16} d +c) n^2.$$
In order for "what you want" to follow from "what you can prove", you argue: If I can choose the parameter $d$ such that
$$\frac{3}{16} d + c \le d,$$
then what I need follows from the inequality I can prove. That's what your prof did, and it turned out that yes, you can find such a positive $d$!
Working with inequalites this way is hard and probably unintuitive to many. That's because often the inequality $A \le C$ you need to prove will be done by finding a suitable $B$ where you can prove $A \le B$ and $B\le C$, and nobody can tell you beforehand how this $B$ looks like.
In this case, $B$ arrived via the recurrence formula, and here you needed to choose $d$ suitable to make $B \le C$ true. Since the definition of $O(n^2)$ says such a $d$ must exist, but can be any positive value, you have that freedom.