ECE 368 Complexity
Studied by 2 people
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/27
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
28 Terms
Adjacency Matrix: check if edge(x,y) exists?
O(1)
Adjacency List: check if edge(x,y) exists?
O(V)
Adjacency Matrix: Find a node’s degree
O(v)
Adjacency List: Find a node’s degree
O(E)
Adding an edge for Adjacency Matrix and Adjacency List
O(1)
Adjacency Matrix: Delete an edge
O(1)
Adjacency List: Delete an edge
O(E)
Adjacency Matrix: Traverse a graph
O(v²)
Adjacency List: Traverse a graph
O(V + E)
Adjacency Matrix: space complexity
O(v²)
Adjacency List: space complexity
O(V + E)
BFS/DFS on adjacency matrix
O(V²)
BFS/DFS for adjacency list
O(V+E)
Dijkstra
O(vlog(v) + Elog(v))
merge sort
O(nlog(n))
quick sort best/average case
O(nlog(n))
quick sort worst case (time complexity)
O(n²)
quick sort space complexity
O(log(n))
BFS on a DAG
O(V + E)
Radix sort
O(nxd) where d = floor(log(n-1)) + 1
counting sort
O(k+n) where k = range of possible values
Bellman-Ford
O(V*E)
Kruskal
O(Elog(E))
Prim space complexity
O(V+E)
bucket sort worst case
O(n²)
bucket sort best case
O(n+k)
Note 
Flashcards (20)