Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
28 Cards in this Set
- Front
- Back
|
Sorting of n elements lower and upper bounds
|
Lower: O(n logn)
Upper: O(n logn) |
|
|
Merge sort complexity
|
O(n logn)
|
|
|
Heap sort complexity
|
O(n logn)
|
|
|
Insert sort complexity
|
O(n^2)
|
|
|
Selection sort complexity
|
O(n^2)
|
|
|
Counting sort complexity
|
O(n)
|
|
|
Find median among n elements complexity
|
Lower: O(n)
Upper: O(n) |
|
|
Find median with decomposition complexity
|
O(n)
|
|
|
Search in sorted n-array complexity
|
Lower: O(n logn)
Upper: O(n logn) |
|
|
Binary search in sorted n-array complexity
|
O(logn)
|
|
|
Textsearch in text of length n complexity
|
Lower: O(n)
Upper: O(n) |
|
|
Knuth-Morris-Pratt Textsearch complexity
|
O(n)
|
|
|
Graf traversal complexity
|
Lower: O(|V| + |E|)
Upper: O(|E|) |
|
|
Breadth First Search of graph complexity
|
O(|E|)
|
|
|
Depth First Search of graph complexity
|
O(|E|)
|
|
|
Prim, Minimal Spanning Tree complexity
|
O(|E| log|V|)
|
|
|
Kruskal, Minimal Spanning Tree complexity
|
O(|E| log|V|)
|
|
|
Djikstra, Shortest path between corners s and t, non-negative edge-weights complexity
|
O(|V|^2)
|
|
|
Dynamic programming, Shortest path between all corners, no cycles with negative length
|
O(|V|^3 log|V|)
|
|
|
Ford Fulkerson, Maximal flow
|
O(|V|^3)
|
|
|
Discrete Fourier Transform (DFT) in n points, using Fast Fourier Transform
|
O(n logn)
|
|
|
Multiplication of two n-degree polynom (unit cost), using Fast Fourier Transform
|
O(n logn)
|
|
|
Decomposition, multiplying two n-bit numbers (bit cost)
|
O(n^1,58)
|
|
|
Fastest known algorithm, multiplying two n-bit numbers (bit cost)
|
O(n logn loglogn)
|
|
|
Strassen (decomposition), multiplying two n * n matrixes
|
O(n^2,81)
|
|
|
Coppersmith and Winograd, multiplying two n * n matrixes
|
O(n^2,376)
|
|
|
Decide if a point is inside a n-sided polygon, couting amount of lines crossed (skärningsräkning)
|
O(n)
|
|
|
Grahamscan, convex hull to n points.
|
O(n logn)
|
