Algorithms / BigO notation guarantees for the cost of insertion and deletion
Sorting Algorithms
1. Merge Sort: O(n log n)
Sort each pair of elements then, sort every four elements by merging every two pairs Then, sort every 8 elements, etc O(n log n) expected and worst case
2. Quick Sort: O(n log n) worst: O(n^2)
Pick a random element and partition the array, such that all numbers that are less than it come before all elements that are greater than it Then do that for each half, then each quar ter, etc O(n
log n) expected, O(n^2) worst case
3. Bucket Sort: O(n + m)
Partition the array into a finite number of buckets, and then sort each bucket individually.
This gives a time of O(n + m), where n is the number of items and m is the number of distinct items
4. Selection Sort: O(n^2)
Find the smallest element using a linear scan and move it to the front Then, find the second smallest and move it, again doing a linear scan Continue doing this until all the elements are in place
O(n^2)
5. Bubble Sort: O(n^2)
Start at the beginning of an array and swap the first two elements if the first is bigger than the second Go to the next pair, etc, continuously making sweeps of the array until sorted O(n^2)
Trees
Binary Search Tree: O(log n)
Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search
https://en.wikipedia.org/wiki/Binary_search_tree
Breadth First Search
Breadthfirst search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neig
https://en.wikipedia.org/wiki/Breadthfirst_search
References:
