Complexities Flashcards
1
Q
What is the complexity for BST
A
Best case search O(1)
Worst case (LL) O(n)
Average case O(logn)
2
Q
Max heap height?
A
O(log n)
3
Q
Heap Creation.
Bottom Up
Top Down
A
O(n) worst case
O(nlogn) worst case
4
Q
Adjacency List
Adjacency Matrix
A
O(|V| + |E|)
O(|V|^2)
5
Q
Topological Sort
A
O(|V|+|E|)
6
Q
Dijkstra’s Algorithm
A
O(|V|^2)
heap: O((|E|+|V|)+log|V|)
shortest path between all pairs O(|V|^3)
7
Q
Kruskal’s Algorithm
A
number of edges = |V| - 1
O(|E|log|V|)
8
Q
Prim’s Algorithm
A
Simple algorithm: O(|V|^2)
Heap: O(|E|log|V|)
9
Q
Hashing Function
A
O(1)
10
Q
Separate chaining
A
Accessing/Finding List O(1)
Finding a key O(n)
