Sí, su comprensión y su respuesta son correctas. Si quieres un análisis más profundo de lo que ocurre con esta relación de recurrencia, recuerda la definición de coeficiente binomial $$(x+y)^k=\sum_{i=0}^k\binom ki x^{k-i}y^i$$
Ahora mira de nuevo el árbol de recursión escrito sin las simplificaciones que has utilizado
![enter image description here]()
Obsérvese que surge un patrón con los coeficientes a $cn$ en cada nivel. Son los coeficientes binomiales con $x = \frac{1}{3}$ y $y = \frac{2}{3}$ . Aquí están los primeros niveles redactados de forma más explícita
![enter image description here]()
Así, la suma del trabajo realizado por los nodos para cada nivel es \begin{align*} \text{Level } 0&: cn = \left( \frac{1}{3} + \frac{2}{3} \right)^0cn\\ \text{Level } 1&: \left(\frac{1}{3}\right)^1\left(\frac{2}{3}\right)^0cn + \left(\frac{1}{3}\right)^0\left(\frac{2}{3}\right)^1cn = \left( \frac{1}{3} + \frac{2}{3} \right)^1cn\\ \text{Level } 2&: \sum_{i=0}^2\binom 2i \left(\frac{1}{3}\right)^{2-i}\left(\frac{2}{3}\right)^i = \left( \frac{1}{3} + \frac{2}{3} \right)^2cn\\ & \vdots \\ \text{Level } k&: \sum_{i=0}^k\binom ki \left(\frac{1}{3}\right)^{k-i}\left(\frac{2}{3}\right)^i = \left( \frac{1}{3} + \frac{2}{3} \right)^kcn\\ \end{align*}
Obsérvese también que la suma del trabajo en los nodos de cada nivel individual hasta este punto es $(1)\cdot cn = cn$ y si hay $k$ niveles hasta ahora, el trabajo total realizado hasta este momento es $cn \cdot k$ . Sin embargo, dado que el subárbol derecho realiza más trabajo que el subárbol izquierdo ( $\frac{2n}{3} > \frac{n}{3}$ ), veremos finalmente que sus nodos hoja (es decir, los casos base) aparecen en un nivel inferior en el árbol y los nodos hoja a lo largo del árbol estarán escalonados.
El siguiente paso es argumentar un límite inferior para la altura del árbol. La hoja más a la izquierda del subárbol izquierdo tendrá una altura $h_{left} = \text{log}_3(n)$ y la hoja más a la derecha del subárbol derecho estará a la altura $h_{right} = \text{log}_{3/2}(n)$ . Esto se basa en los coeficientes binomiales en esos lugares, con $\left(\frac{1}{3}\right)^k\left(\frac{2}{3}\right)^0 = \left(\frac{1}{3}\right)^k$ en la hoja más a la izquierda y $\left(\frac{1}{3}\right)^0\left(\frac{2}{3}\right)^k = \left(\frac{2}{3}\right)^k$ en la hoja más a la derecha. Así que $k = h_{left}$ se produce cuando $n = \left(\frac{1}{3}\right)^k \Rightarrow k = \log_3(n)$ y $k = h_{right}$ se produce cuando $n = \left(\frac{2}{3}\right)^k \Rightarrow k = \log_{3/2}(n)$ .
Como buscamos un límite inferior, utilizaremos $h_{left} = \text{log}_3(n)$ . Consideremos un árbol binario completo con altura $2^{\text{log}_3(n)}$ formado tomando nuestro árbol de recurrencia y cortando todos los nodos a la derecha pasado este nivel y convirtiendo los nodos restantes en este último nivel en nodos hoja. Claramente, esto da un límite inferior ya que hemos excluido los nodos escalonados de nivel superior en el subárbol de la derecha. Por lo tanto (asumiendo un valor de $T_1$ a nivel de hoja) un límite inferior para $T(n)$ viene dada por \begin{align*} T(n) &\ge (\text{work done by leftmost leaves}) + (cn \cdot h_{left}) \\ T(n) &\ge T_1 \cdot 2^{\text{log}_3(n)} + cn\cdot\text{log}_3(n) \\ &= T_1 \cdot n^{\text{log}_3(2)} + cn\cdot\text{log}_3(n) && \text{by properties of logarithms}\\ &\approx T_1 \cdot n^{1.6} + cn\cdot\text{log}_3(n) \\ &= \Omega(n\text{lg}n) \end{align*}
