2 votes
Accepted

Bound $T$ asymptotically tight | Recursive trees

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$.     ...
codeR's user avatar
  • 98
2 votes

Bound $T$ asymptotically tight | Recursive trees

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|...
Steven's user avatar
  • 29.4k

Only top scored, non community-wiki answers of a minimum length are eligible