Big-O Cheat Sheet
ADVERTISEMENT
1
2Big-O Cheat Sheet
Generated December 10, 2013.
Brandon Amos <
1
Searching
Algorithm
Data Structure
Time Complexity
Space Complexity
Average
Worst
Depth First Search (DFS)
Graph of
vertices and
-
(
+
)
(
)
edges
Breadth First Search
Graph of
vertices and
-
(
+
)
(
)
(BFS)
edges
Binary search
Sorted array of n elements
(log( ))
(log( ))
(1)
( )
( )
(1)
Linear (Brute Force)
Array
Shortest path by Dijkstra,
using a Min-heap as prior-
Graph with
vertices
((
+
) log
)
((
+
) log
)
(
)
ity queue
and
edges
Shortest path by Dijkstra,
(
)
using an unsorted array as
Graph with
vertices
priority queue
and
edges
Shortest path by Bellman-
Graph with
vertices
(
)
(
)
(
)
Ford
and
edges
1
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education