Mathematical Analysis of recursive Algorithm

i) Decide the input size based on the parameter n.

ii) Identify the algorithm’s basic operation.

iii) Check how many times the basic operation is executed and if it depends on the input size n then identify the best,worst and average case efficiency has be analysed separately.

iv) Setup the recurence relation with some intial condition and expressing the basic operation

v) Solve the recurence relation using the forward or backward substitution method and then correctness of formula can be proved with the help of mathematical induction method.

Example:Tower of Honai

Mathematical Analysis of recursive Algorithm

Algm toh (n,a,c,b)
{
if(n==1) then
{
write (“the weight is moved from a to c”)
return
}
else
{
toh(n-1,a,b,c) //Moving n-1 weight from a to b using c
toh(n-1,b,c,a) //Moving n-1 weight from b to c using a
}
}

Latest posts by admin (see all)

More in sem4
Asymptotic Notations

Asymptotic Notations Asymptotic Notations are methods to estimate and represent efficiency of the algorithm using simple formula To choose the...

Close