Page 299 Exercise 4

Sollin's algorithm is quite elegant, and has a complexity far better than Prim's algorithm.  Using the example that appears in Figure 6.25 of the text, it is quite obvious that Sollin's algorithm makes only two passes over the graph before the spanning tree is completed.  Each pass adds ⌈ _n/2⌉ edges to the tree.  For the example in the text, ⌈_7/2 ⌉ = 4 edges are added on the first pass.  The remaining 2 edges ⌈_4/2⌉ are added on the second pass.  The complexity of this algorithm is slightly better than log₂n.