Intro To Algorithms Flashcards
Requirements of an Algorithm
Steps need to be in a very specific order
Steps also need to be distinct
Algorithm should produce a result
Completes in finite amount of time
Order of Growth or growth rate
How an algorithm performs as input set increases.
Standard for evaluating an algorithm.
Big O
Order of magnitude of completely.
Theoretical definition of the complexity of an algorithm as a function of the size.
Notation used to describe complexity.
O(n)
Only helpful in comparing algorithms that solve the same problem.
Upper bounds of algorithm (how it performs in worst case.)
O(1)
Constant time operation.
Runtime per operations is constant throughout the algorithm.
Linear time
Time it takes to run through a whole list in order or
O(log n)
Binary search complexity.
O = Order of magnitude of Complexity
Log= logarithm of N.
N= function of the size (size of list / array? Variable)
Order of run times by Big O notation
O(1) or Constant Time (checking to see if one variable matches another.
O (log n)
O (n)
O (n log n)
O (n^2)
O (n^k)
O(n log n)
O(n!)
Logarithm of N
When double value of N, number of operations only increases by 1. Also the inverse of an exponent.
O (ln n)
Another notation for logarithmic time. Same as O (log n).
Sublinear
Logarithmic run times which are faster than linear run times ?(or any run time below that)?
Quadratic Time
(remember a quadratic equation is when something is squared) O(n^2)
Cubic Runtime
O(n^3) less common, very computationally expensive.
Quasilinear Runtimes
O(n log n)
Between linear and quadratic run time.
Common in sorting algorithm.
Polynomial Runtime
Any algorithm where worst case run time is O(n^k) power. Considered efficient.
Factorial or Combinatorial run time
Factorial = 4! = 4x3x2x1 = 24
O(n!)
