User:Mital.vora/AlgorithmAndDataStructureComplexities
Algorithms and DataStructure Complexities
data structure
Trees
| Name | Invented By | Invented Year | Average Space | Worst Space | Average Search | Worst Search | Average Insert | Worst Insert | Average Delete | Worst Delete |
|---|---|---|---|---|---|---|---|---|---|---|
Binary Search Tree
|
O(n) | O(n) | O(log n) | O(n) | O(log n) | O(n) | O(log n) | O(n) | ||
| B-tree | Rudolf Bayer, Edward M. McCreight | 1972 | O(n) | O(n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
Red Black Tree
|
Rudolf Bayer | 1972 | O(n) | O(n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL tree | E. M. Landis
|
1962 | O(n) | O(n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
Sorting Algorithms
know how they work, average/worst case running times, stack space
| Name | Data Structure | Worst Time | Best Time | Average Time | Space | Optimal? | Stability |
|---|---|---|---|---|---|---|---|
Insertion Sort
|
Array
|
О(n2) | O(n) | О(n2) | О(n) total, O(1) auxiliary | No | |
Quick Sort
|
O(n2) | O(n log n) | O(n log n) | O(n) auxiliary (naive) O(log n) auxiliary (Sedgewick 1978) |
No | Not Stable | |
Merge Sort
|
Array
|
O(n log n) | O(n log n) typical,
O(n) natural variant |
O(n log n) | O(n) auxiliary | Yes | |
Heap Sort
|
Array
|
O(n log n) | , O(n log n)[1] | O(n log n) | O(n) total, O(1) auxiliary | Never |
References
External links