Difference between pages "4.35" and "8.3"

Latest revision as of 14:06, 21 September 2020

No. Counter example provided below:

G(V,E,W) = ((A,B,C,D),({A,B},{B,C},{C,D},{D,A}),(1,2,3,4))

Minimum spanning tree has a weight of 6 with edges {A,B},{B,C},{C,D}.

In the full graph the minimum distance between A and D is 4.

@@ Line 1: / Line 1: @@
-It's not clear to me if the first <math>n - \sqrt n</math> element being sorted means that the remaining <math>\sqrt n</math> elements are all bigger or not, but let's suppose they are not, since that's more general.
+No. Counter example provided below:
-First sort the remaining <math>\sqrt n</math> elements in <math>O(\sqrt n \log \sqrt n)</math> time. After that we can do a simple merge step to merge the two sorted arrays in <math>O(n)</math> time. Since <math>\sqrt n</math> dominates <math>\log \sqrt n</math> we can come to the conclusion that the total running time of this algorithm is: <math>O(\sqrt n \log \sqrt n + n) = O(\sqrt n \sqrt n + n) = O(n + n) = O(n)</math>
+G(V,E,W) = ((A,B,C,D),({A,B},{B,C},{C,D},{D,A}),(1,2,3,4))
+Minimum spanning tree has a weight of 6 with edges {A,B},{B,C},{C,D}.
-Back to [[Chapter 4]]
+In the full graph the minimum distance between A and D is 4.
+Back to [[Chapter 8]]