Final Review Flashcards
1
Q
Time complexity of naive string matcher.
A
Preprocessing = 0
worst matching time = O((n-m+1)m)
Average matching time with few spurious hits = O(n-m + 1)
2
Q
Time complexity of Rabin-Karp
A
Preprocessing = theta(m)
Matching time = O(n-m+1)m)
3
Q
Time complexity of Finite automaton
A
Preprocessing = O(m|E|)
Matching time = theta(n)
Total time including preprocessing =
4
Q
Time complexity of KMP
A
Preprocessing - theta(m)
Matching time = O(n)
Total = O(m+n)
5
Q
Time complexity of adjacency list
A
O(V) + O(E)
6
Q
Time complexity of adjacency matrix
A
O(V^2)
7
Q
Graph Union
A
O(n^2)
8
Q
BFS
A
queueing = O(V) Total = O(V+E)
9
Q
DFS
A
O(V+E)
10
Q
All-pairs shortest paths
A
O(V^3)
11
Q
Matirix Multiplication
A
O(n^3)
12
Q
Quick sort
A
O(nlogn)
13
Q
Binary search
A
O(logn)
14
Q
Linear
A
O(n)
15
Q
Parsing over string twice
A
O(n^2)
16
Q
Dijkstra’s time complexity
A
O(VE + E*log(V))
