patternMinor
How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?
Viewed 0 times
thenonthanbetteralgorithmsrecursivehowandadmitthey
Problem
How are asymptotical time complexities calculated for recursive algorithms?
Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they better taking time complexity into account? If they are better than non-recursive algorithms, then how are they better and why (not)?
Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they better taking time complexity into account? If they are better than non-recursive algorithms, then how are they better and why (not)?
Solution
Typically, by writing a recurrence relation for the running time and then solving the recurrence relation. See How to come up with the runtime of algorithms? and Solving or approximating recurrence relations for sequences of numbers. You might also want to read your friendly textbook and Is there a system behind the magic of algorithm analysis?.
Context
StackExchange Computer Science Q#55823, answer score: 7
Revisions (0)
No revisions yet.