Recursive Algorithms Complexity: Difference between revisions
| (7 intermediate revisions by the same user not shown) | |||
| Line 9: | Line 9: | ||
=Recurrence= | =Recurrence= | ||
A '''recurrence''', or a <span id='Recurrence_Equation'></span>'''recurrence equation''', is an equation or an inequality that describe the running time of a recursive algorithm for a problem of size n in terms of the running time on smaller inputs. Once the running time is expressed this way, we can use mathematical tools or other methods to [[#Solving_Recurrences|solve the recurrence]], which means obtaining asymptotic bounds on the running time of the algorithm. | A '''recurrence''', or a <span id='Recurrence_Equation'></span>'''recurrence equation''', is an equation or an inequality that describe the running time of a recursive algorithm for a problem of size n in terms of the running time on smaller inputs. Once the running time is expressed this way, we can use mathematical tools, such as the [[Master_Method|master method]] or other methods to [[#Solving_Recurrences|solve the recurrence]], which means obtaining asymptotic bounds on the running time of the algorithm. | ||
As an example, the following recurrence expresses the running time for merge sort: | |||
<font size=-1> | |||
│ c if n == 1 | |||
T(n) = │ | |||
│ 2T(n/2) + cn if n > 1 | |||
</font> | |||
More details on recurrences and how master methods uses recurrences to predict running time are available in: {{Internal|Master_Method#Master_Method_and_Recurrences|Master Method and Recurrences}} | |||
=Solving Recurrences= | =Solving Recurrences= | ||
| Line 19: | Line 27: | ||
==<span id='Recursion_Tree'></span>Recursion-Tree Method== | ==<span id='Recursion_Tree'></span>Recursion-Tree Method== | ||
{{Internal|Recursion Trees|Recursion Trees}} | |||
==<span id='The_Master_Theorem'></span><span id='Master_Theorem'></span>The Master Method (Master Theorem)== | ==<span id='The_Master_Theorem'></span><span id='Master_Theorem'></span>The Master Method (Master Theorem)== | ||
{{Internal|Master Method|Master Method}} | {{Internal|Master Method|Master Method}} | ||
Latest revision as of 23:29, 19 October 2021
Internal
Overview
The running time of recursive algorithms can be analyzed using recurrences.
Recurrence
A recurrence, or a recurrence equation, is an equation or an inequality that describe the running time of a recursive algorithm for a problem of size n in terms of the running time on smaller inputs. Once the running time is expressed this way, we can use mathematical tools, such as the master method or other methods to solve the recurrence, which means obtaining asymptotic bounds on the running time of the algorithm.
As an example, the following recurrence expresses the running time for merge sort:
│ c if n == 1
T(n) = │
│ 2T(n/2) + cn if n > 1
More details on recurrences and how master methods uses recurrences to predict running time are available in:
Solving Recurrences
There are at least three method to solve recurrences:
Substitution Method
The method consists in guessing a bound and then using mathematical induction on the recurrence to prove the solution correct. We can guess a solution using a recursion tree. Examples on how to use mathematical induction to prove the bound is correct are available in CLRS page 83.