From efdba76e6fdbcbdf1ce1c217d3a35dfb9ade5f79 Mon Sep 17 00:00:00 2001 From: Jonas Smedegaard Date: Mon, 21 Apr 2025 15:08:51 +0200 Subject: document complexity of function isConnected() --- .../bachelorizer/model/Combi.java" | 7 +++++++ 1 file changed, 7 insertions(+) diff --git "a/dk/abcdefghijklmnopqrstuvxyz\303\246\303\270\303\245/bachelorizer/model/Combi.java" "b/dk/abcdefghijklmnopqrstuvxyz\303\246\303\270\303\245/bachelorizer/model/Combi.java" index 85227a7..077b317 100644 --- "a/dk/abcdefghijklmnopqrstuvxyz\303\246\303\270\303\245/bachelorizer/model/Combi.java" +++ "b/dk/abcdefghijklmnopqrstuvxyz\303\246\303\270\303\245/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 -- cgit v1.2.3