Complexities

Question 1

What is the complexity for BST

Answer 1

Best case search O(1)
Worst case (LL) O(n)
Average case O(logn)

Question 2

Max heap height?

Answer 2

O(log n)

Question 3

Heap Creation.
Bottom Up
Top Down

Answer 3

O(n) worst case
O(nlogn) worst case

Question 4

Adjacency List
Adjacency Matrix

Answer 4

O(|V| + |E|)
O(|V|^2)

Question 5

Topological Sort

Answer 5

O(|V|+|E|)

Question 6

Dijkstra’s Algorithm

Answer 6

O(|V|^2)
heap: O((|E|+|V|)+log|V|)
shortest path between all pairs O(|V|^3)

Question 7

Kruskal’s Algorithm

Answer 7

number of edges = |V| - 1
O(|E|log|V|)

Question 8

Prim’s Algorithm

Answer 8

Simple algorithm: O(|V|^2)
Heap: O(|E|log|V|)

Question 9

Hashing Function

Answer 9

O(1)

Question 10

Separate chaining

Answer 10

Accessing/Finding List O(1)
Finding a key O(n)