Discrete Mathematics
Discrete mathematicsis the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics -- such as integers, graphs, and statements in logic-- do not vary smoothly in this way, but have distinct, separated values.Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus or Euclidean geometry. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets(finite sets or sets with the same cardinality as the natural numbers). However, there is no exact definition of the term "discrete mathematics."Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.
The set of objects studied in discrete mathematics can be finite or infinite. The termfinite mathematicsis sometimes applied to parts of the field of discrete mathematics that deals with finite sets, particularly those areas relevant to business.
https://en.wikipedia.org/wiki/Discrete_mathematics
Recurrence Relation
A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing Fn as some combination of Fi with i<n).
Example − Fibonacci series − Fn = Fn−1 + Fn−2 Fn = Fn−1 + Fn−2, Tower of Hanoi − Fn = 2 Fn − 1 + 1
1. Linear Recurrence Relations
A linear recurrence equation of degree k or order k is a recurrence equation which is in the formatxn=A1xn−1+A2xn−1+A3xn−1+...Akxn−k (Anis a constant andAk≠0) on a sequence of numbers as a first-degree polynomial.
2. Non-Homogeneous Recurrence Relation
A recurrence relation is called non-homogeneous if it is in the form
Fn=AFn−1+BFn−2+f(n)wheref(n)≠0
Its associated homogeneous recurrence relation is Fn=AFn--1+BFn−2
https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_recurrence_relation.htm
In mathematics, arecurrence relationis an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given; each further term of the sequence or array is defined as a function of the preceding terms.
The term difference equation sometimes (and for the purposes of this article) refers to a specific type of recurrence relation. However, "difference equation" is frequently used to refer to any recurrence relation.
Fibonacci numbers
The recurrence of order two satisfied by the Fibonacci numbers is the archetype of a homogeneous linear recurrence relation with constant coefficients. The Fibonacci sequence is defined using the recurrence
Fn = Fn-1 + Fn-2
https://en.wikipedia.org/wiki/Recurrence_relation
Common Recurrence Relations
| Recurrence | Algorithm | Big-Oh Solution |
|---|---|---|
| T(n) = T(n/2) + O(1) | Binary Search | O(log n) |
| T(n) = T(n-1) + O(1) | Sequential Search | O(n) |
| T(n) = 2 T(n/2) + O(1) | tree traversal | O(n) |
| T(n) = T(n-1) + O(n) | Selection Sort (other n^2^sorts) | O(n^2^) |
| T(n) = 2 T(n/2) + O(n) | Mergesort (average case Quicksort) | O(n log n) |