Im trying to prove the following using induction but I am stuck with a constant in my induction step which I can't rid of:
$T\left(n\right)=T\left(\left\lfloor\alpha n\right\rfloor\right)+T\left(\left\lfloor(1-\alpha)n\right\rfloor\right)+1=O\left(n\right) \ \ \ \ for\ \ \ \alpha<1.$
Target: want to show for a specific constant $c>0$ and "big enough" $ n $ that $T\left(n\right)\le c\cdot n$
base case:
Assuming $T(0)=1$ and showing for $n=1$:
For every constant $c\geq3 $ , the folloing it true: $T\left(1\right)=T\left(\left\lfloor\alpha\right\rfloor\right)+T\left(\left\lfloor(1-\alpha)\right\rfloor\right)+1\le1+1+1=3\le c\cdot1$
induction step: $ T\left(n\right)=T\left(\left\lfloor\alpha n\right\rfloor\right)+T\left(\left\lfloor(1-\alpha)n\right\rfloor\right)+1\le\ c\cdot\left\lfloor\alpha n\right\rfloor+\ c\cdot\left\lfloor(1-\alpha)n\right\rfloor+1\le c\cdot an+\ c\cdot(1-\alpha)n+1\le cn+1$
And this is where I get stuck
I would like to say someting like $\left\lfloor a n\right\rfloor+\left\lfloor(1-\alpha)n\right\rfloor\le n-1$ , but well, it is not accurate for exampla in case $\alpha=\frac{1}{3}$ and $n=9$
Any assistance would be appreciated!
Let $f(n) = T(n)+1$; then the recurrence relation for $T(n)$ becomes $$ T(n) + 1 = T(\lfloor \alpha n\rfloor) + 1 + T(\lfloor (1-\alpha) n\rfloor) + 1 $$ after we add $1$ to both sides, and this simplifies to $$ f(n) = f(\lfloor \alpha n\rfloor) + f(\lfloor(1-\alpha)n\rfloor). $$ We can begin by proving $f(n) = O(n)$; now, the approach you're taking will work just fine, because the inequality we need is $\left\lfloor \alpha n\right\rfloor+\left\lfloor(1-\alpha)n\right\rfloor\le n$, and this is always true.
This means $T(n) = O(n)$ because $T(n) \le f(n)$.