Report On Proof Of Akra Bazzi's Master Theorem. 3f6r3u

Report on proof of generalized Master theorem and its variations Mayank Singh August 30, 2010 B.Tech, 3rd year student Computer Science and Engineering IIT Rajasthan,India Abstract Akra and Bazzi had given a generalization of the Master Method that provides a very simple formula for solving most divide-and-conquer problems.Tom Leighton has proved Akra Bazzi’s formula and also extended it to some more variations.In this report,I will discuss what i had learned from the proof and what are modifications possible along limitations of Akra Bazzi’s formula. Advantages of Akra Bazzi’s formula over regular Master Theorem:• Recurrence can contain any number of having there a0i s and b0i s may be different or same whereas in regular Master theorem it has only one value of ai and bi . Thus it is more generalised form of Master Theorem. • The Master Theorem given in Cormen, Leiserson and Rivest is true for f(n) that are polynomially bounded. But it is not true for all polynomially bounded functions. For example: when f (n) is smaller than nlogb a but not polynomially smaller. Similarly, when f (n) is larger than nlogb a but not polynomially larger. But such cases do not exist for Akra-Bazzi s Master Theorem. Limitations of Akra Bazzi’s formula :Pk • The boundation for ai ’s and bi ’s is i=1 ai bpi = 1 which is very important. Without this we cannot proof the generalized Master Theorem. • Similarly the function g(x) should satisfies the polynomial growth condition. If not, then proof of its cannot be given.

1

Some important concepts in proof :• Polynomial Growth Condition :If there exist positive constants c1 ,c2 such that for all x ≥ 1, for all 1 ≤ i ≤ k, and for all u ∈ [bi x, x], c1 g(x) ≤ g(u) ≤ c2 g(x) If |g 0 (x)| is upper bounded by a polynomial in x, then g(x) satisfies the polynomial growth condition. • If g(x) is a non negative function that satisfies the polynomial-growth condition,then there are positive constants such that for all x ≥ 1, for all 1≤i≤k , Z x g(u) ≤ c4 g(x) c3 g(x) ≤ xp p+1 u bi x

Note on variation of akra and bazzi’s result:With the akra bazzi formula we can calculate simple recursions but if recursions are inequalities then we need to add a function h(x) with each b(x). Now the function will look like somewhat this:

T (x) =

θ(1) for 1 ≤ x ≤ x0 ; a T (b x + h (x)) + g(x) for x > x0 ; i i i=1 i

Pk

We can choose h0i s such that |hi | < 1 ,representing ceiling functions such as hi (x) = dbi xe − bi x √ also we choose large h0i s, such as hi = − x thus the variations covers a more larger recursive functions than Akra Bazzi’s formula. References :• Thomas H. Cormen, Charles E. Leierson, and Ronald L. Rivest. Introduction to Algorithms.The MIT Press, Cambridge, Massachusetts, 1990. • Notes on Better Master Theorems for Divide-and-Conquer Recurrences.Tom Leighton , 1996.

2