Big O Notation Flashcards
linear search best case time complexity
O(1)
linear search average case time complexity
O(n)
linear search worst case time complexity
O(n)
Binary search array best case time complexity
O(1)
Binary search array average case time complexity
O(log n)
Binary search array worst case time complexity
O(log n)
Binary search tree best case time complexity
O(1)
Binary search tree average case time complexity
O(log n)
Binary search tree worst case time complexity
O(n)
Hashing best case time complexity
O(1)
Hashing average case time complexity
O(1)
Hashing worst case time complexity
O(n)
Breadth/depth-first of graph best case time complexity
O(1)
Breadth/depth-first of graph average case time complexity
O(V+E)
Breadth/depth-first of graph worst case time complexity
O(V^2)
Bubble sort best case time complexity
O(n)
Bubble sort average case time complexity
O(n^2)
Bubble sort worst case time complexity
O(n^2)
Bubble sort space complexity
O(1)
Insertion sort best case time complexity
O(n)
Insertion sort average case time complexity
O(n^2)
Insertion sort worst case time complexity
O(n^2)
Insertion sort space complexity
O(1)
Merge sort best case time complexity
O(n log n)
Merge sort average case time complexity
O(n log n)
Merge sort worst case time complexity
O(n log n)
Merge sort space complexity
O(n)
Quick sort best case time complexity
O(n log n)
Quick sort average case time complexity
O(n log n)
Quick sort worst case time complexity
O(n^2)
Quick sort space complexity
O(log n)
Meaning of O(1)
Constant
same time regardless of size of data set
Meaning of O(log n)
Logarithmic
halves the data set in each pass
opposite of exponential
directly proportional to logarithmic result of input size
Meaning of O(n)
Linear
time increases proportional to size of data set
Meaning of O(n log n)
Linearithmic
Meaning of O(n^2)
Polynomial
time increases proportional to square of size of data set
nested loops
Meaning of O(2^n)
Exponential
doubles with each addition to data set in each pass
opposite to logarithmic
