Sprouting Graphs

Given \(n\) vertices \(v_1,v_2,v_3, .. , v_n\), we generate a graph \(G\) as follows:

  • Go through each pair of vertices \(v_i,v_j\)

  • Flip a coin

  • If the coin is heads, create an edge \(E_{ij}\) between \(v_i,v_j\)

Now, suppose we have two of these random graphs \(G_1\) and \(G_2\). We want to determine if they are the same. Your task is to find the best case expected time of the most efficient algorithm we could come up with to do this.

The best case expected time \(T\) can be said to satisfy \[ T = \Theta( n^a ) \]

for some integer \(a\). Find \(a\).


Problem Loading...

Note Loading...

Set Loading...