$T(n)=T(cn) + T((1-c)n)+1$ while $0<c<1$

Question: $T(n)=T(cn) + T((1-c)n)+1$

$0<c<1$ and $T(1)$ is constant.

My thoughts: I'm trying to solve this recursion using Induction, but I think I got it all wrong.

My guess is that $T(n) = O(n)$

The induction assumption:

for every $k<n$ exists a constant $m$ that $T(k) < mn $

because $0<c<1$ we know that $cn<n$ and $(1-c)n<n$

Therefore $T(cn)<mn$ and $T((1-c)n)<mn$

I need to prove that $T(n)<mn$

so I said that $T(n) = T(cn) + T((1-c)n)+1 < mn +mn +1 = 2mn+1$

But now my constant has changed to $m'=2m$ which is a problem...

what can I do?

I hadn't studied any fancy sentences.. I can use induction, recursion trees or something simple...

any help would be highly appreciated! Thanks

If $T(n)=T(cn) + T((1-c)n)+1$ then let $S(n)={T(n)+1}$.

You have $S(n)=S(cn) + S((1-c)n)$ or equivalently $S(a+b)=S(a)+S(b)$, with the linear solution $S(n)=nS(1)$.

So $T(n)+1=n(T(1)+1)$, i.e. $$T(n)=nT(1)+n-1$$ which is indeed $O(n)$

By Archimedean principle, $\exists M\in \mathbb{Z}$ such that $(M-2m)n>1\Rightarrow T(n)<Mn$. So, $T(n)=O(n)$.

Let, for $k<n$, $T(n)<m_k n$ for some $m_k$. Then, since both $cn,\ (1-c)n$ are $<n$, $T(n)=T(cn)+T((1-c)n)+1<(m_1+m_2)n+1<m_3n$ for some $m_1,m_2,m_3$.