Big O Flashcards
Complexity
how well the performance of an algorithm scales as the size of data sets increase.
time complexity
the number of steps/line of code executed in an algorithm.
space complexity
the memory requirement for an algorithm
efficiency
time complexity and space complexity
BigO
a complexity notation. remove all coefficiants and just write the value of n with the largest exponent e.g. O(n)
O(1)
constant complexity
constant complexity
An algorithm that always executes in the same time regardless of the size of the data set. Efficient with any data set.
O(log n)
Logarithmic Complexity
Logarithmic Complexity
An algorithm that halves the data set in each pass. Efficient with large data sets. Good algorithms.
O(n)
Linear Complexity
Linear Complexity
An algorithm whose performance is proportional to the size of the data set and declines as the data set grows. Fair algorithms.
O(n^a)
Polynomial complexity (quadratic, cubic etc)
Polynomial complexity (quadratic, cubic etc)
An algorithm whose performance is proportional to the square of the size of the data set. Significantly reduces efficiency with increasingly large data sets. Poor algorithms.
O(2^n)
Exponential Complexity
Exponential Complexity
An algorithm that doubles with each addition to the data set in each pass. Inefficient. Extremely poor algorithms that should be avoided.
O(n log N)
Algorithms that divide a data set but can be solved using concurrency on independent divided lists.
complexity order
O(1) -> O(logn) -> O(n) -> O(nlogN) -> O(n^2) -> O(2^n)
Linear search best
O(1)
linear search average
O(n)
