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)
linear search worst
O(n)
binary search best
O(1)
binary search average
O(logn)
binary search worst
O(logn)
Binary search tree best
O(1)
Binary search tree average
O(logn)
Binary search tree worst
O(n)
Hashing best
O(1)
HAshing average
O(1)
Hashing worst
O(n)
Breadth/Depth first best
O(1)
Breadth/Depth first average
O(V+E)
V = no. vertices
E = no edges
Breadth/Depth first worst
O(V^2)
Bubble sort best
O(n)
Bubble sort average
O(n^2)
Bubble sort worst
O(n^2)
Bubble sort space complexity
O(1)
Insertion sort Best
O(n)
Insertion sort Average
O(n^2)
Insertion sort Worst
O(n^2)
Insertion sort Space complexity
O(1)
Merge sort best
O(nlogn)
Merge sort average
O(nlogn)
Merge sort worst
O(nlogn)
Merge sort Space complexity
O(n)
Quick Sort best
O(nlogn)
Quick Sort average
O(nlogn)
Quick Sort Worst
O(n^2)
Quick sort space complexity
O(logn)
