Skip to content

Latest commit

 

History

History
25 lines (22 loc) · 1.38 KB

time-complexity-graph-data-structures.asc

File metadata and controls

25 lines (22 loc) · 1.38 KB

Summary

In this section, we learned about Graphs, applications, properties, and how we can create them. We mention that you can represent a graph as a matrix or as a list of adjacencies. We went for implementing the latter since it’s more space-efficient. We cover the basic graph operations like adding and removing nodes and edges. In the algorithms section, we are going to cover searching values in the graph.

Table 1. Time and Space Complexity for Graph-based Data Structures

Data Structure

Searching By

Insert

Delete

Space Complexity

Index/Key

Value

BST (unbalanced)

-

O(n)

O(n)

O(n)

O(n)

BST (balanced)

-

O(log n)

O(log n)

O(log n)

O(n)

Hash Map (naïve)

O(n)

O(n)

O(n)

O(n)

O(n)

HashMap (optimized)

O(1)

O(n)

O(1)*

O(1)

O(n)

TreeMap (Red-Black Tree)

O(log n)

O(n)

O(log n)

O(log n)

O(n)

HashSet

O(1)

-

O(1)*

O(1)

O(n)

TreeSet

O(log n)

-

O(log n)

O(log n)

O(n)

* = Amortized run time. E.g. rehashing might affect run time to O(n).