# Bound $T$ asymptotically tight | Recursive trees

Let $$\alpha \in (0, 1),\space l \geq 2$$ and $$T: \mathbb{N}\rightarrow\mathbb{R}^+$$ such that,

$$T(n) = \begin{cases} n^l + T(\alpha n) + T((1-\alpha)n) & : n > 1 \\1 : n=1 \end{cases}$$

Bound $$T$$ asymptotically tight.

So I understand that I need to split into cases, the first one is where $$\alpha < \frac{1}{2}$$ and $$\alpha \geq \frac{1}{2}$$.
However, I struggle to bound $$T$$ tightly at each case (I only know how to bound it from one side).
I'd like to understand the general idea\strategy in situations like this.

We can directly approach this problem using the recurrence tree method. Let us now denote $$1-\alpha$$ as $$\beta$$ for notational clarity. For any constant $$l\ge2$$ we have, $$\alpha^l+\beta^l < 1$$.

$$T(n)$$ ----------------------- work = $$n^l=n^l(\alpha^l+\beta^l)^0$$

/                \

$$T(\alpha n)$$                 $$T(\beta n)$$ ------------ work = $$(\alpha n)^l+(\beta n)^l=n^l(\alpha^l+\beta^l)$$

/          \                 /          \

$$T(\alpha^2 n)$$ $$T(\alpha\beta n)$$ $$T(\alpha\beta n)$$ $$T(\beta^2 n)$$ --- work = $$\small(\alpha^2 n)^l+(\alpha\beta n)^l+(\alpha\beta n)^l+(\beta^2 n)^l=n^l(\alpha^l+\beta^l)^2$$

$$\vdots$$             $$\vdots$$              $$\vdots$$             $$\vdots$$

Thus, $$T(n) \le \sum\limits_{i=0}^{\log_{1/\max(\alpha,\beta)} n}n^l(\alpha^l+\beta^l)^i \le \sum\limits_{i=0}^{\infty} n^l(\alpha^l+\beta^l)^i = \frac{n^l}{1-(\alpha^l+\beta^l)} = O(n^l)$$

Similarly, $$T(n) \ge \sum\limits_{i=0}^{\log_{1/\min(\alpha,\beta)} n}n^l(\alpha^l+\beta^l)^i \ge n^l = \Omega(n^l)$$

Therefore, $$T(n) = \Theta(n^l)$$

PS: One can derive the tight expressions for both the GP series, but the amsymptotic bounds remain the same, so I have opted for very loose bounds.

Using the Akra-Bazzi method we have that $$\alpha^p + (1-\alpha)^p = 1$$ for $$p=1$$, and that: $$\int_1^n \frac{x^l}{x^{p+1}} \, \text{d}x = \int_1^n x^{l-2} \, \text{d}x= \frac{x^{l-1}}{l-1} \,\bigg|_{x=1}^{n} = \Theta(n^{l-1}).$$

Hence: $$T(n) = \Theta\Big( n^p \cdot \big(1 + \int_1^n \frac{x^l}{x^{p+1}} \, \text{d}x ) \Big) = \Theta\big( n \cdot (1 + n^{l-1}) \big) = \Theta(n^l).$$