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

Question

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

$0<c<1$ $T(1)$ es constante.

Mis pensamientos: Estoy tratando de resolver este recursividad el uso de la Inducción, pero yo creo que lo tengo todo mal.

Mi conjetura es que el $T(n) = O(n)$

La inducción de la asunción:

para cada $k<n$ existe una constante $m$ que $T(k) < mn $

debido a $0<c<1$ sabemos que $cn<n$ $(1-c)n<n$

Por lo tanto, $T(cn)<mn$ $T((1-c)n)<mn$

Necesito demostrar que $T(n)<mn$

así que me dijo que $T(n) = T(cn) + T((1-c)n)+1 < mn +mn +1 = 2mn+1$

Pero ahora mi constante ha cambiado a $m'=2m$ que es un problema...

¿qué puedo hacer?

Yo no había estudiado sentencias de lujo.. Puedo usar la inducción, la recursividad de los árboles o algo simple...

cualquier ayuda sería muy apreciada! Gracias

Answer 1

Si $T(n)=T(cn) + T((1-c)n)+1$ a continuación, vamos a $S(n)={T(n)+1}$.

Ha $S(n)=S(cn) + S((1-c)n)$ o, equivalentemente,$S(a+b)=S(a)+S(b)$, con el lineal de la solución de $S(n)=nS(1)$.

Por lo $T(n)+1=n(T(1)+1)$, es decir,$$T(n)=nT(1)+n-1$$ which is indeed $ O(n)$

Answer 2

Por el principio de Arquímedes, $\exists M\in \mathbb{Z}$ tal que $(M-2m)n>1\Rightarrow T(n)<Mn$. Por eso, $T(n)=O(n)$.

---

Supongamos, por $k<n$, $T(n)<m_k n$ para algunos $m_k$. Entonces, ya que tanto $cn,\ (1-c)n$ $<n$, $T(n)=T(cn)+T((1-c)n)+1<(m_1+m_2)n+1<m_3n$ para algunos $m_1,m_2,m_3$.