diff options
| author | Jonas Smedegaard <dr@jones.dk> | 2025-04-21 15:08:51 +0200 |
|---|---|---|
| committer | Jonas Smedegaard <dr@jones.dk> | 2025-04-21 15:08:51 +0200 |
| commit | efdba76e6fdbcbdf1ce1c217d3a35dfb9ade5f79 (patch) | |
| tree | 3e3ca52e973daf5350637f0b280172b622bad9a9 | |
| parent | 204a494c6f345ddac62c83f2bcc6492d3e949c74 (diff) | |
document complexity of function isConnected()
| -rw-r--r-- | dk/abcdefghijklmnopqrstuvxyzæøå/bachelorizer/model/Combi.java | 7 |
1 files changed, 7 insertions, 0 deletions
diff --git a/dk/abcdefghijklmnopqrstuvxyzæøå/bachelorizer/model/Combi.java b/dk/abcdefghijklmnopqrstuvxyzæøå/bachelorizer/model/Combi.java index 85227a7..077b317 100644 --- a/dk/abcdefghijklmnopqrstuvxyzæøå/bachelorizer/model/Combi.java +++ b/dk/abcdefghijklmnopqrstuvxyzæøå/bachelorizer/model/Combi.java @@ -77,6 +77,13 @@ public final class Combi { /// If check fails, throw an unchecked exception, /// since it occurs at runtime and is unrecoverable. /// + /// Complexity of the operation is O(min(2n,n²,n*m+1)) + /// where n is the amount of vertices and m is amount of edges, + /// since visitDepthFirst() recurses out-edges of all vertices, + /// and a connected graph has at least one out-edge per vertex + /// (arguably complexity is merely O(2n,n²) + /// since an unconnected graph is treated an as exception). + /// /// @param g Graph to inspect /// @throws IllegalArgumentException /// https://docs.oracle.com/javase/tutorial/essential/exceptions/runtime.html |