factorial program complexity code example

Example: complexity analysis of factorial using recursion

T(n) = T(n-1) + 3   (3 is for As we have to do three constant operations like 
                 multiplication,subtraction and checking the value of n in each recursive 
                 call)

     = T(n-2) + 6  (Second recursive call)
     = T(n-3) + 9  (Third recursive call)
     .
     .
     .
     .
     = T(n-k) + 3k
     till, k = n

     Then,

     = T(n-n) + 3n
     = T(0) + 3n
     = 1 + 3n