Mathematical Analysis of Recursive Algorithm.

Guide line of Mathematically analysis of Recursive algorithm with example.
using forward and backsword substitution method.

1. Mathematical analysis of recursive algorithm B h a r a t i . C M . t e c h

2. General plans for analysis of recursive algorithm 1 ) decide the input size . 2 ) identify th e basic operation . 3 ) check how many time the basic operation performed and determine the best worst and average case . 4 ) se t u p a recursive relation with some initial condition expressing the basic operation . 5 ) solve recursion with using forward and backward substitution and correct formula using mathematical induction .

3. A l g o rithm : factorial ( n ) i f ( n = = ) r e t u r n 1 e l s e r e t u r n f a c t ( n - 1 ) * n

4. Mathematical analysis : Step 1 : input size is n step 2 : basic operation is multiplication step 3 : recursive function i s F ( n ) = F ( n - 1 ) * n w h e r e n > S t e p 4 : m u l t i p l i c ation i s g i v en a s M ( n ) = M ( n - 1 ) + 1

5. S t e p 4 : F orwords substitution : M ( n ) = M ( n - 1 ) + 1 M ( ) = n = M ( 1 ) = M ( 1 - 1 ) + 1 = 1 . . . . . . . . . . . . . . n = 1 M ( 2 ) = M ( 2 - 1 ) + 1 = 2 . . . . . . . . . . . . . . . . . n = 2 M ( 3 ) = M ( 3 - 1 ) + 1 = 3

6. Backward substitution : M ( n ) = M ( n - 1 ) + 1 M ( n ) = [ M ( n - 2 ) + 1 ] + 1 = M ( n - 2 ) + 2 M ( n ) = [ M ( n - 3 ) + 1 ] + 2 = M ( n - 3 ) + 3 M ( n ) = M ( n - i ) + i

7. Now we correct the formula P r o v e : M ( n ) = n b y u s i ng m a t h ematical i n d u c t ion L e t n = M ( n ) = . M ( ) = = n I n d u c tion : M ( n - 1 ) = n - 1 M ( n ) = M ( n - 1 ) + 1 = n - 1 + 1 = n M ( n ) = n T i m e c o m p l e x ity . ( n )

8. T h a n k you