Core User Guide: Run-time Characteristics

The current Graph representation is based on a mutable hash set. Unfortunately, immutable Graphs have no separate persistent representation.

In terms of the Big-O notation, operation costs on graphs can be summarized as follows:

Operation Cost
mutable immutable
Instance Creation O(V + E)
element addition O(1) O(V + E)
element removal O(1) O(V + E)
element look-up O(1)
traversal O(V + E)
path search O(V + E)
shortest path search O(VlogV + E)

Algorithms are tail recursive so they are guaranteed not to cause any stack overflow.