Recursive Algorithms Complexity: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(13 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 run time of a recursive algorithm for a problem of size n in terms of the running time on smaller inputs. Once the run 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 run 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=
 
There are at least three method to solve recurrences:
There are at least three method to solve recurrences:


===Substitution Method===
==Substitution Method==


The method consists in guessing a bound and then using [[Mathematical_Induction|mathematical induction]] on the [[#Recurrence|recurrence]] to prove the solution correct. We can guess a solution using a [[#Recursion_Tree|recursion tree]]. <font color=darkgray>Examples on how to use mathematical induction to prove the bound is correct are available in [[CLRS]] page 83.</font>
The method consists in guessing a bound and then using [[Mathematical_Induction|mathematical induction]] on the [[#Recurrence|recurrence]] to prove the solution correct. We can guess a solution using a [[#Recursion_Tree|recursion tree]]. <font color=darkgray>Examples on how to use mathematical induction to prove the bound is correct are available in [[CLRS]] page 83.</font>


===<span id='Recursion_Tree'></span>Recursion-Tree Method===
==<span id='Recursion_Tree'></span>Recursion-Tree Method==
 
{{Internal|Recursion Trees|Recursion Trees}}
The method consists in converting the recurrence into graphical tree representation whose nodes represent costs incurred at various level of the recursion. After we lay out the tree, we sum the costs within each level of the tree to obtain a set of per-level costs, then we sum all the per-level costs to determine the total cost of the recursion. The bound such guessed can be proven with the [[#Substitution_Method|substitution method]]. <font color=darkgray>Examples on how to build recursion trees are available in [[CLRS]] page 37 and page 88.</font>
 
===<span id='The_Master_Theorem'></span><span id='Master_Theorem'></span>The Master Method (Master Theorem)===
 
The <span id='Master_Method'></span>'''master method''' is a method of analyzing running time of recursive algorithms by using the "master theorem". The master theorem applies to algorithms whose running times can be expressed as a [[#Recurrence_Equation|recurrence equation]]. A generic form of a recurrence equation is:


T(n) = a⋅T(n/b) + f(n)
==<span id='The_Master_Theorem'></span><span id='Master_Theorem'></span>The Master Method (Master Theorem)==
 
where a ≥ 1, b > 1 and f(n) is a function that approximates the non-recursive cost. Note that the above expression does include a boundary condition for n = 1. The reasons is that T(1) does not significantly change the solution to the recurrence, it may change it with a constant factor, but the order of growth will stay unchanged.
 
<font color=darkgray>TODO [[CLRS]] page 93.</font>
 
<font color=darkkhaki>TODO integrate after class:</font>
{{Internal|Master Method|Master Method}}
{{Internal|Master Method|Master Method}}
==Analyzing Divide-and-Conquer Algorithms==
<font color=darkkhaki>TODO integrate after class:</font>
For [[Algorithms#Divide_and_Conquer|divide-and-conquer recursive problems]], where solving the problem involves dividing the problem into ''a'' subproblems of size ''n/b'' of the original', applying the algorithm recursively ''a'' times on ''n/b''-size problems and then combining the result, the run time can be expressed by the generic recurrence presented below. If the problem size is small enough (n ≤ c) the straightforward solution takes constant time, which is expressed as a constant function [[#Constant_Function|Θ(1)]].
        | Θ(1)                    if n ≤ c
T(n) = |
        | aT(n/b) + D(n) + C(n)    otherwise
where the D(n) is the cost of dividing the n-size problem into a subproblems, and the C(n) is the cost of combining the results.
<br>
<center>&#91;[[Algorithm_Complexity#Recursive_Algorithms_Complexity|Next]]]</center>

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:

Master Method and Recurrences

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.

Recursion-Tree Method

Recursion Trees

The Master Method (Master Theorem)

Master Method
Retrieved from "https://kb.novaordis.com/index.php?title=Recursive_Algorithms_Complexity&oldid=84170"