Analysis of Algorithms 2.5

Card Set Information

Author:
eaavendano
ID:
121802
Filename:
Analysis of Algorithms 2.5
Updated:
2011-12-08 02:42:43
Tags:
recurrence relations
Folders:

Description:
Recurrence Relations
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user eaavendano on FreezingBlue Flashcards. What would you like to do?


  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

What would you like to do?

Home > Flashcards > Print Preview