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

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
}
}