akra bazzi formula for calculating time complexity

Shiv Dutt Jha — Fri, 14 Jan 2022 10:46:39 +0000

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)

Form Validation Using html and javascript

Shiv Dutt Jha — Fri, 14 Jan 2022 10:43:10 +0000

https://codepen.io/Shivay7992/project/editor/ZKQLKJ

DEV Community: Shiv Dutt Jha

akra bazzi formula for calculating time complexity

Form Validation Using html and javascript