Algorithm Complexities Flashcards
(25 cards)
What is the best case time complexity of all searching algorithms?
O(1) (because it is the found at the first item examined)
Average time complexity of a linear search?
O(n)
Average time complexity of a binary search on an array?
O(log n)
Average time complexity of a binary search on a tree?
O(log n)
Average time complexity of a hashing algorithm?
O(1)
Average time complexity of a breadth/depth first search
O(V + E) (vertices + edges, equivalent to O(n) )
Worst case time complexity of a linear search?
O(n)
Worst case time complexity of a binary search on an array?
O(log n)
Worst case time complexity of a binary search on a tree?
O(n)
Worst case time complexity of a hashing algorithm?
O(n) (because the value has been stored in the overflow table, so linear searches through all of its items)
Worst case time complexity of a breadth/depth first search
O(V^2) (vertices^2)
Best case time complexity of a bubble sort?
O(n)
Best case time complexity of an insertion sort?
O(n)
Time complexity in any case of a merge sort?
O(n log n)
Best case time complexity of a quick sort?
O(n log n)
Average time complexity of a bubble sort?
O(n^2)
Average time complexity of an insertion sort?
O(n^2)
Average time complexity of a quick sort?
O(n log n)
Worst case time complexity of a bubble sort?
O(n^2)
Worst case time complexity of an insertion sort?
O(n^2)
Worst case time complexity of a quick sort?
O(n^2)
Space complexity of a bubble sort?
O(1)
Space complexity of an insertion sort?
O(1)
Space complexity of a merge sort?
O(n)
