Akira
Akira
Programming language:Whatever
2021-08-06 20:59:11
0
Q:

complexity analysis of factorial using recursion

Mutturaj
Mutturaj
Code: Whatever
2021-08-21 23:00:21 
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
0

Tags

Related

New to Communities?

Join the community