I need to prove T(N) = O(N)
$T(n) = T([3N/4] )+ T([N/4] ) + 1$
I think a good way to solve is to prove that T(N) < N-1
Induction hypotysis: for N-1, prove for N:
$T(n) = T([3N/4])+ T([1N/4]) + 1 < [3N/4] - 1 + [N/4] - 1+1<N-1$
now here is my question (it might be a stupid). because n>n-1, it should be easier to prove $T(N) < N $ but when I'm tring to prove $T(N)<N$ I'm stucked.
$T(n) = T([3N/4])+ T([N/4]) + 1 < [3N/4] + [N/4] +1 <= N+ 1$
what am I doing wrong?
Let $T(n) \le cn-d$, where $c$, $d$ are constants $>0$.
For $n = 0$, by the recurrence relation, $T(0) = T\left(\left\lfloor\frac{3\times0}{4}\right\rfloor\right) + T\left(\left\lfloor\frac{0}{4}\right\rfloor\right) + 1 = T(0)+T(0)+1$, i.e. $T(0) = -1$. If we take $d=1$, then the inequality holds for $n=0$.
Now assume, for some non-negative integer $k$, the statement is true for all integers from $0$ to $k$.
For $n=k+1$, $$\begin{align} T(k+1) =& T\left(\left\lfloor\frac{3(k+1)}{4}\right\rfloor\right) + T\left(\left\lfloor\frac{k+1}{4}\right\rfloor\right) + 1\\ \le& c\left\lfloor\frac{3(k+1)}{4}\right\rfloor-1 + c\left\lfloor\frac{k+1}{4}\right\rfloor-1 + 1 &\text{(by assumption)}\\ \le& \frac{3(k+1)c}{4} + \frac{(k+1)c}{4} - 1\\ \le& c(k+1) - 1\\ \end{align}$$
Now, if we take $c=1$, the assumption and induction steps still hold. Therefore, $T(n) \le n-1$, or $T(n)=O(n)$.
After I try to make a proof, I understands the problem you encountered. If you simply assume $T(n) < n$, this assumption is too weak for you to prove $T(n+1) < n+1$. Instead, if you make a stronger assumption of $T(n) \le n-1$, you will be able to do the induction step.
By the way, if there is no base case ($T(0)$) given, and all I know is that $T(0) = -1$, then I can also take the $c$ above to be zero, and the induction step still works. I can even prove $T(n) = -1$ by induction. If this is not the case, check if your inductive proof did consider the base case.
