# 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)