Analysis of Algorithms 2.5

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
Analysis of Algorithms 2.5
Recurrence Relations
Show Answers