Dear all,

I have a solution to another problem and I would greatly appreciate any assistance to help me verify the solution to it. . This one is from Thomas Coreman. It goes as follows:-


The recurrence T(n) = 7T(n/2) + n² describes the running time of algorithm A. There is another competing algorithm A' = T(n) = aT(n/4) + n². What is the largest integer value of "a" so that A' is asymptotically faster than A?

My initial intuition for the solution was to first determine the running time of A. Then find the value of variable "a" in A' so that the running time of A' is exactly same as A. The answer will then be a-1.

From the master theorem, n^log₂7 = 2.81. therefore f(n) = TEHTA(n²) = BIGOH(n^2.81-e) where e = 0.81. Therefore T(n) = THETA(n^2.81).


Now for A' to be THETA(n^2.81), a has to be 49 as log₄49 = 2.81. The largest int value of a so that A' is faster is therefore 48. since then A' = THETA(n^2.79) approx.