I am fairly new algorithms and the math behind it.
I am very sorry if this is the wrong place to ask if so please let me know and I can delete this question.
I would need help with the following algorithms.
The task is to choose α so that B is asymptotically faster than A.
A: $\ T_a$(n) = 7$T_a$($\frac{n}{2}$)+n²
B: $\ T_b$(n) = α$T_b$($\frac{n}{4}$)+n²
I have tried to figure out what the asymptotically upper bound would be and I have come up with this formula for A:
A: T(n) = n² + $\sum_{k=1}^k 7^{k-1} \frac{(n^2)}{2^k}+7^kT(\frac{n}{2^k})$
k is for n < 2 = ld(n)
But I do not understand how to go on from here.
Any help would be very apricated.
If you are familiar with Master theorem, you can solve it easily. From the master theorem as $c_{crit} = \log_27 \sim 2.81$ we know that $A = O(n^{2.81}) = \Theta(n^{\log_27})$. Hence, if $a = 4^2 = 16$, from master thorem $B = \Theta(n^2\log(n))$ and asymptotically faster than $A$. Also, for all $a < 16$ this would be true.