Analysis of Algorithms 2.5

Home > Preview

The flashcards below were created by user eaavendano on FreezingBlue Flashcards.

1. Closed-Form Solution
An equation or formula in which a value can be substituted in order to get a correct output back directly.
2. Linear
A recurrence relation for a sequence if the earlier values of the sequence appearing in the definition occur only to the 1st power.
3. Constant Coefficients
Values in an equation which do not change.
4. First-Order
A situation in which the nth term depends only on term n - 1.

S(n) = cS(n - 1) + g(n)
5. Homogeneous
A recurrence relation in which the term g(n) = 0 for all n.

S(n) = cS(n - 1) + g(n)
6. Characteristic Equation
The key to the solution of the recurrence relation:

• S(n) c1S(n - 1) + c2S(n - 2)
• is the quadratic equation:

t2 - c1t - c2 = 0

Card Set Information

 Author: eaavendano ID: 121802 Filename: Analysis of Algorithms 2.5 Updated: 2011-12-08 07:42:43 Tags: recurrence relations Folders: Description: Recurrence Relations Show Answers:

Home > Flashcards > Print Preview