With probability , we'll connect 1-2 or 3-4, leading to the same connectedness. With probability , we'll connect 1 or 2 with 3 or 4. Therefore, the expected time is .

I did it with dynamic programming. First I used disjoint sets (or connected components would work fine) to calculate the sizes of all the connected components of the graph. Then, my recursive dynamic programming state was a sorted list of those sizes (the total number of states is somewhere around the 30th partition number. At each state I did the following sum:

For each pair of element of my list of sizes, the number of edges I could add is just the product of their sizes — call this p. Since there are n choose 2 total edges in the graph, the probability that I connect these components is p / (n choose 2). So I add to my sum p / (nchoose 2) * (1 + dp(new list with these components combined)).

However, if I add up the probabilities for all of these combinations, they may not sum to 1 since there's the case when I add in an edge to the same component. For this, just observe the following formula, letting x be the probability that I choose two nodes in the same component: dp(list) = (sum above) + x * (1 + dp(list))

This can be rewritten as dp(list) = ((sum above) + x) / (1 — x)

You can calc only one row from matrix, all others will be same with shift. O(lg(K)*N^2)