1
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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). $$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.