Mathematical Analysis of Nonrecursive Algorithms

1) Decide on parameter(s) indicating an input’s size.

2) Identify algorithm’s basic operation.

3) Check whether the number of times the basic operation is performed depends only on the size of the input. If it also depends on some additional property, the worst case, average-case, and best case performance times should be determined separately.

4) Set up the sum expressing the number of times the basic operation is performed.

5) Calculate the sum or at least establish its order of growth.

EXAMPLES

· Find largest item in a given array

· Check whether all the elements in a given array are distinct.

· Given two n-by-n matrices A and B, find the time efficiency of the definition based algorithm to compute their product.

· Find the number of binary digits in the binary representation of a positive decimal integer.

Mathematical analysis of Recursive Algorithms

1) Decide on parameter(s) indicating an input’s size.

2) Identify algorithm’s basic operation.

3) Check whether the number of times the basic operation is performed depends only on the size of the input. If it also depends on some additional property, the worst case, average-case, and best case performance times should be determined separately.

4) Set up the recurrence relation with an appropriate initial condition for the number of times the basic operation is performed.

5) Solve the recurrence or at least provide the order of growth of its solution.

EXAMPLES

· Compute factorial of a nonnegative integer n.

Fact(0) = 1

Fact(n) = n _* Fact(n-1)

M(0) = 0

M(n) = M(n-1) + 1

· Tower of Hanoi

· Recursive algorithm to determine the number of digits in binary representation of a positive decimal integer n.

Binrec(n)

if n=1

return 0

else

return BinRec(n/2)+1

A(n) = A(n/2)+1

A(1) = 0

· Fibonacci Numbers

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

F(0)=0

F(1)=1

F(n)= F(n-1)+F(n-2) n>=2

Homogeneous second order linear recurrence with constant coefficients.

a x(n) + b x(n-1) +c x(n-2)=0

a,b,c real numbers, a not equal to 0.

a r² + b r + c =0

r1=(1+ sqrt(5))/2

r2=(1 - sqrt(5))/2