Question

The recurrence t(n)=7t(n/2)+n2 describes the running time of an algorithm a

Answer 1

Answer:

From the question the given recurrence relation is T(n)=7T(n/2)+n^2 while its solution is by the master theorem of asymptotic complexity T(n)=Θ(n^log49base4). So, the general formulate of the complexity can be given as the recurrence relation T′(n)=αT′(n/4)+n^2.

So, from the relation we have that, a=α,b=4,f(n)=n^2

n^loga base b=n^logα base 4, for the value of the α>16, f(n)=O(n^logα−ξ) where the ξ>0.

Therefore, for α>16: T′(n)=Θ(n^logα base 4)

Now A has to hold, for becoming asymptotically faster than A':-

n^logα base 4<n^log49 base 4 since the base is e so equating the power we will get:- logα base 4<log49 base 4 So, on solving we will get α<49.

Consequently the value of α so that A′ is asymptotically faster than A will bet the value of 48.