HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?

Submitted by: @import:stackexchange-cs··
0
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)?

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.