how to solve f(n) = f((3/4)n) + f(n^(1-b)) + c n^b

98 Views Asked by Yegane At 28 April 2025 at 07:03

How can I solve this recurrence :

f(n) = f((3/4)n) + f(n^(1-b)) + c n^b

where b and c are constants and 0<b<1 and f(1)=1

There are 1 best solutions below

OmG On 24 December 2020 at 14:49

We cannot directly use Akra-Bazzi theorem as you have mentioned, because we cannot write $n^{1-b}$ in the form of $b \times n + h(n)$ such that and $h(n) = O\left(\frac{n}{log(n)^2}\right)$ which is required for utilizing the theorem. However, we can find an upper bound by substituting $f(n^{1-b})$ with $f(d\times n)$ such that $d$ is constant and less than $1$ . Now, we can use akra-bazzi theorem for $f(n) = f(3/4 n) + f(d\times n) + c n^b$ . To continue, first we need to solve $p$ in the following equation:

$\left(\frac{3}{4} \right )^p + d^p = 1$

As we know in the integral part we have $\int_{1}^{n}\frac{u^b}{u^{1+p}} du$ , if we choose $d$ such that $p = b$ , the upper bound is $O(n^b \log(n))$ .

Hence, we can choose $d = \left(1 - \left(\frac{3}{4}\right)^b\right)^{\frac{1}{b}}$ which is less than $1$ and a constant.

how to solve f(n) = f((3/4)n) + f(n^(1-b)) + c n^b

There are 1 best solutions below

Related Questions in ALGORITHM

Related Questions in TIME-COMPLEXITY

Related Questions in RECURRENCE

Related Questions in MASTER-THEOREM

Trending Questions

Popular # Hahtags

Popular Questions