Algorithm analysis recurrence comparision

Question

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.

Answer 1

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 

Answer 2

The solution should be something similar to this one but you should consider the floor and ceil.

For algorithm X we have:

T(n)=7T(n/2)+n^2
=> O(n)=n^2 + 7(n/2)^2 + 49(n/2)^3 + ... + 7^log(n)(n/2)^(log(n)+1)
=> O(n)=n^2 . [7/(2^2) + 7^2/2^3 + ... + 7^log(n)/2^(log(n)+1)]
=> O(n)=n^2 . \sum_{i=1 to log(n)}{1/2x(7/2)^i}   <= geometrical series summation easy

and follow the same for the Y Until you can compare and find the value of a.