A stronger way to solve $T\left ( n \right )= 2T\left ( n/4 \right )+ n^{1/2+ \epsilon}$ where $\epsilon= 0.01$, excluding the Master theorem

52 Views Asked by At

I want to ask you a further way to solve $T\left ( n \right )= 2T\left ( n/4 \right )+ n^{1/2+ \epsilon}$ where $\epsilon= 0.01$, excluding the Master theorem.
By Master theorem, we have $b= a^{2}$ and $f\left ( n \right )= \Omega\left ( n^{1/2+ \epsilon} \right )$ and the regularity condition holds, then $T\left ( n \right )= \Theta\left ( f\left ( n \right ) \right )$ for $f\left ( n \right )= n^{1/2+ \epsilon}$.
How could we deal the $\epsilon= 0.01$ of the new stronger algorithm? For example, using $\ln 2\ln 2+ \epsilon< 1/2$.
I need your help. Thank you so much!

1

There are 1 best solutions below

0
On BEST ANSWER

Hint.

Make $n=4^m$ and the recurrence recast to

$$ r_m = 2r_{m-1}+\left(4^m\right)^{\frac 12+\epsilon} $$

with solution

$$ r_m= 2^{m-1}c_0+\frac{2^m\cdot 4^{(m+1)\epsilon}-2^{m+2\epsilon}}{4^{\epsilon}-1} $$