Let algorithms X: T(n) = 7T(n/2)+n^2, and Y: T’(n) = aT’(n/4)+n^2
I need to find the largest value for a
, such that algorithm Y
is asymptotically faster than algorithm X
.
Using masters theorem :-
X : T(n) = O(n^log2(7))
So to get an asymptotically faster algorithm using masters theorem
2 <= log4(a) < log2(7)
Finding max value such that the condition is true :-
log4(a) < log2(7)
log2(a)/log2(4) < log2(7)
log2(a)/2 < log2(7)
log2(a) < 2*log2(7)
a < 7^2 = a < 49
As a is no of subproblems it needs to be integer therefore :-
a = 48 is max value that a can take so that Y is asymptotically faster than X