The Akra-Bazzi method
The master method does not apply to a recurrence such as
T(n)=T(n/3)+T(2n/3)+O(n)
In such case, we use another more powerful and general method known as Akra-Bazzi method. The Akra-Bazzi method solves the recurrence relation of the form
T(n)=∑i=1kaiT(bin)+f(n)
where,
ai>0 is a constant for i≤i≤k
bi∈(0,1) is a constant for 1≤i≤k
k≥1 is a constant and,
f(n) is non-negative function
The solution of recurrence given in (2) is,
T(n)=Θ(np(1+∫n1f(u)up+1du))
Provided,
∑i=1kaibpi=1 where p is a unique real number.
Example 1: Consider a recurrence,
T(n)=2T(n/4)+3T(n/6)+Θ(nlogn)
For this recurrence, a1=2,b1=1/4,a2=3,b2=1/6,f(n)=nlogn. The value of p can be calculated as,
a1bp1+a2bp2=2×(1/4)p+3×(1/6)p=1
p=1 satisfies the above equation.
The solution is
T(n)=Θ(np(1+∫n1f(u)up+1du))=Θ(n(1+∫n1uloguu2du))=Θ(n(1+log2n2))=Θ(nlog2n)
Top comments (0)