Question

3. (25 points) Let TA and Te be two function returning the running time of algorithms A and B, defined by the recusions TA(n) T(2 and TR(n) T(2n2. Find the largest integer value of a for which algorithm B is asymptotically faster than A. Show your work and justify your answer in the PDF file. Answer in the MyCourses quiz.

Answer 1

T_A=7T_A(n/2)+n².

Applying master's methon , solution to this recurrence is : O(n^log₂7).

Now, consider the second recurrence:

$T_B=\alpha T_B(n/4)+n^2.$

Now for value of $\alpha<16$ , solution to this recurrence will be O(n²).

for value of $\alpha=16$ , solution to this recurrence will be O(n²log₂ⁿ).

for value of $\alpha>16$ , solution to this recurrence will be $O(n^{log_4\alpha})$ , which is asymptotically not faster than

O(n^log₂7).

So, 16 is the largest integer for $\alpha$ , so that B is faster than A.