Parallel Algorithms: Difference between revisions

Parallel Algorithms (view source)

499 bytes added , 21 April 2020

5,323

edits

@@ Line 538: / Line 538: @@
 ;Theorems
+* The pointer graph always consists of rooted trees.
+* For every vertex which is not a leaf, <math>D(v) \leq v</math>
 ;Complexity
+* Time <math>O(\log n)</math>
+* Work <math>O((n+m)\log n)</math>
+{{ hidden | Proof |
+Let <math>h(T)</math> be the height of tree T where a two-layer tree has height 1.<br>
+Define a single node to have height 1.<br>
+Let <math>H</math> be the sum of heights of all trees and <math>\bar{H}</math> be the total height after one iteration.
+* Claim: <math>\bar{H} \leq 2*H/3</math>
+}}
 ===Minimum Spanning Forest===