Analysis of Algorithms 2.5
Home
>
Flashcards
> Print Preview
The flashcards below were created by user
eaavendano
on
FreezingBlue Flashcards
. What would you like to do?
Get the free app for
iOS
Get the free app for
Android
Learn more
Closed-Form Solution
An equation or formula in which a value can be substituted in order to get a correct output back directly.
Linear
A recurrence relation for a sequence if the earlier values of the sequence appearing in the definition occur only to the 1st power.
Constant Coefficients
Values in an equation which do not change.
First-Order
A situation in which the
n
th term depends only on term
n
- 1.
S(n) = cS(n - 1) + g(n)
Homogeneous
A recurrence relation in which the term
g(n) = 0
for all
n.
S(n) = cS(n - 1) + g(n)
Characteristic Equation
The key to the solution of the recurrence relation:
S(n) c
_{1}
S(n - 1) + c
_{2}
S(n - 2)
is the quadratic equation:
t
^{2}
- c
_{1}
t - c
_{2}
= 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:
What would you like to do?
Get the free app for
iOS
Get the free app for
Android
Learn more
Home
>
Flashcards
> Print Preview