title: Running time of Kruskal's algorithm
body: <p>The Kruskal's algorithm is the following:</p>
  
  <pre><code>MST-KRUSKAL(G,w)
  1. A={}
  2. for each vertex v∈ G.V
  3.      MAKE-SET(v)
  4. sort the edges of G.E into nondecreasing order by weight w
  5. for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight w
  6.      if FIND-SET(u)!=FIND-SET(v)   
  7.         A=A U {(u,v)}  
  8.         Union(u,v)
  9. return A
  </code></pre>
  
  <p>According to my textbook:</p>
  
  <blockquote>
    <p>Initializing the set A in line 1 takes O(1) time, and the time to sort
    the edges in line 4 is O(E lgE). The for loop of lines 5-8 performs
    O(E) FIND-SET and UNION operations on the disjoint-set forest. Along
    with the |V| MAKE-SET operations, these take a total of O((V+E)α(V))
    time, where α is a very slowly growing function. Because we assume
    that G is connected, we have |E| &lt;= |V|-1, and so the disjoint-set
    operations take O(E α(V)) time. Moreover, since α(V)=O(lgV)=O(lgE),
    the total running time of Kruskal's algorithm is O(E lgE). Observing
    that |E|&lt;|V|^2, we have lg |E|=O(lgV), and so we can restate the
    running time of Kruskal's algorithm as O(E lgV).</p>
  </blockquote>
  
  <p>Could you explain me why we deduce that the time to sort the edges in line 4 is O(E lgE)?
  Also how do we get that the total time complexity is  O((V+E)α(V)) ? </p>
  
  <p>In addition, suppose that all edge weights in a graph are integers from 1 to |V|. How fast can you make Kruskal's algorithm run? What if the edges weights are integers in the range from 1 to W for some constant W?</p>
  
  <p>How does the time complexity depend on the weight of the edges?</p>
  
  <p><strong>EDIT</strong>:  </p>
  
  <blockquote>
    <p>In addition, suppose that all edge weights in a graph are integers
    from 1 to |V|. How fast can you make Kruskal's algorithm run?</p>
  </blockquote>
  
  <p>I have thought the following:</p>
  
  <p>In order the Kruskal's algorithm to run faster, we can sort the edges applying Counting Sort.</p>
  
  <ul>
  <li>The line 1 requires O(1) time.</li>
  <li>The lines 2-3 require O(v) time.</li>
  <li>The line 4 requires O(|V|+|E|) time.</li>
  <li>The lines 5-8 require O(|E|α(|V|)) time.</li>
  <li>The line 9 requires O(1) time.</li>
  </ul>
  
  <p>So if we use Counting Sort in order to solve the edges, the time complexity of Kruskal will be </p>
  
  <p><img src="https://i.stack.imgur.com/REHRT.png" alt="enter image description here"></p>
  
  <p>Could you tell me if my idea is right?</p>
  
  <p>Also:</p>
  
  <blockquote>
    <p>What if the edges weights are integers in the range from 1 to W for
    some constant W?</p>
  </blockquote>
  
  <p>We will again use Counting Sort. The algorithm will be the same. We find the time complexity as follows:</p>
  
  <ul>
  <li>The line 1 requires O(1) time.</li>
  <li>The lines 2-3 require O(|V|) time.</li>
  <li>The line 4 requires O(W+|E|)=O(W)+O(|E|)=O(1)+O(|E|)=O(|E|) time.</li>
  <li>The lines 5-8 require O(|E|α(|V|)) time.</li>
  <li>The line 9 requires O(1) time.</li>
  </ul>
  
  <p>So the time complexity will be:</p>
  
  <p><img src="https://i.stack.imgur.com/0NPh7.png" alt="enter image description here"></p>