Como se mencionó en el comentario, las dos primeras condiciones $T(1) = 0, T(2) = 1$ es incompatible con
la última condición
$$\requieren{cancel}
T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lceil\frac{n}{2}\rceil) = 2\quad\text{ para }
\color{red}{\cancelto{\;\color{black}{n > 2}\;}{\color{color gris}{n \ge 2}}}
\etiqueta{*1}$$
en $n = 2$. Vamos a asumir la condición $(*1)$ sólo es válida para $n > 2$ lugar.
Deje $\displaystyle\;f(z) = \sum\limits_{n=2}^\infty T(n) z^n\;$ ser la generación de la función
para que la secuencia de $T(n)$. Multiplicar el $n^{th}$ plazo de $(*1)$ $z^n$ y empezar a sumar de a $n = 3$, obtenemos:
$$\begin{array}{rrl}
&f(z) - z^2 &= T(3) z^3 + T(4) z^4 + T(5) z^5 + \cdots\\
&&= (T(2) + 2)z^3 + (T(2) + T(2) + 2)z^4 + (T(2)+T(3)+2)z^5 + \cdots\\
&&= (1+z)^2 ( T(2)z^3 + T(3)z^5 + \cdots) + 2(z^3 + z^4 + z^5 + \cdots)\\
&&= \frac{(1+z)^2}{z}f(z^2) + \frac{2z^3}{1-z}\\
\implies & f(z) &= \frac{(1+z)^2}{z}f(z^2) + z^2\left(\frac{1+z}{1-z}\right)\\
\implies & \frac{(1-z)^2}{z} f(z) &= \frac{(1-z^2)^2}{z^2}f(z^2) + z(1-z^2)
\end{array}
$$
Sustituto $z^{2^k}$ $z$ en la última expresión y suma más de $k$, obtenemos
$$f(z)
= \frac{z}{(1-z)^2}\sum_{k=0}^\infty \left(z^{2^k} z^{3\cdot2^k}\right)
= \left( \sum_{m=1}^\infty m z^m \right)\sum_{k=0}^\infty \left(z^{2^k} z^{3\cdot2^k}\right)$$
Con esta expresión, podemos leer en $T(n)$ como el coeficiente de $z^n$ $f(z)$ y obtener
$$T(n) = \sum_{k=0}^{\lfloor \log_2 n\rfloor} ( n - 2^k ) - \sum_{k=0}^{\lfloor \log_2(n/3)\rfloor} (n - 3\cdot 2^k)$$
Para $n > 2$, podemos simplificar esto como
$$\bbox[4pt,border: 1px solid black;]{
T(n) =
n \color{red}{\big(\lfloor \log_2 n\rfloor - \lfloor \log_2(n/3)\rfloor\big)}
- \color{blue}{\big( 2^{\lfloor \log_2 n\rfloor + 1} - 1 \big)}
+ 3\color{blue}{\big( 2^{\lfloor \log_2(n/3)\rfloor +1} - 1\big)}}\etiqueta{*2}$$
Hay varias observaciones que podemos hacer.
Al $n = 2^k, k > 1$, tenemos
$$T(n) = n(k - (k-2)) - (2^{k+1} - 1) + 3(2^{k-1} - 1) = \frac32 n - 2$$
Al $n = 3\cdot 2^{k-1}, k > 0$, tenemos
$$T(n) = n(k - (k-1)) - (2^{k+1} - 1) + 3(2^k - 1) = \frac53 n - 2$$
Para $2^k < n < 3\cdot 2^{k-1}, k > 1$, el coeficiente de $n$ $(*2)$ (i.e el factor en color rojo) es $2$, mientras que el resto (me.e aquellos en color azul) no cambian con el $k$.
Por lo $T(n)$ es no lineal con pendiente $2$.
- Para $3\cdot 2^{k-1} < n < 2^{k+1}, k > 1$, el coeficiente de $n$ $(*2)$ ahora es de 1.
Una vez que la ganancia $T(n)$ es lineal ahí, pero con pendiente $1$ lugar.
Combinar estos, encontramos en general
$$\frac32 n - 2 \le T(n) \le \frac53 n - 2 \quad\text{ for }\quad n > 2$$
y $T(n) = O(n)$ como se esperaba. Sin embargo, $\frac{T(n)}{n}$ no concurre
cualquier número, pero oscilan "entre" $\frac32$$\frac53$.
![$T(n) - (\frac32 n - 2)]()
Arriba hay una foto ilustrating el comportamiento de $T(n)$. El azul ventajas son la
valor de $T(n) - (\frac32 n - 2)$ calculado para varios $n$. La línea roja
es $\frac{n}{6} = (\frac53 n - 2) - (\frac32 n - 2)$. Como se puede ver, $T(n)$
no concurre ninguna línea recta. En su lugar, oscilan entre
líneas de $\frac32 n - 2$ $\frac53 n - 2$ como se discutió antes.
