Recursion Trees: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 4: Line 4:
<font color=darkkhaki>Redo after class.</font>
<font color=darkkhaki>Redo after class.</font>


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>
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 [[Recursive_Algorithms_Complexity#Substitution_Method|substitution method]]. <font color=darkgray>Examples on how to build recursion trees are available in [[CLRS]] page 37 and page 88.</font>


<center>&#91;[[Recursive_Algorithms_Complexity#Recursion-Tree_Method|Next in Algorithm Complexity]]]</center>
<center>&#91;[[Recursive_Algorithms_Complexity#Recursion-Tree_Method|Next in Algorithm Complexity]]]</center>

Revision as of 16:03, 21 September 2021

Internal

Overview

Redo after class.

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. Examples on how to build recursion trees are available in CLRS page 37 and page 88.

[Next in Algorithm Complexity]