Libraion's blog

By Libraion, history, 7 weeks ago,

I'm trying to generate a testcase so that Prim with complexity $O(N^2)$ is significantly faster than Prim with priority queue $O((N + M)log(N + M)$ (Here $N$ is number of vertices and $M$ is number of edges).

However as I generate with random weight of the edges the two algorithm runs with nearly the same amount of time (I generate with $N = 2500$ and $M = N * (N - 1) / 2$ (As polygon doesn't allow bigger constraint)).

I wonder if there is a way to construct such test (that for example, the priority queue contains many elements while running...).

Thanks.

• +89

 » 7 weeks ago, # |   0 Are you able to provide the source code of your implementations? I suspect that you did not implement the first version correctly.
•  » » 7 weeks ago, # ^ |   0 https://ideone.com/6O6oxwThis is the $O(N^2)$ version. The problem is to find the total weight of Minimum Spanning Tree.
 » 7 weeks ago, # |   +89 Reading the input is slower than other standard operations. If the input size is $M$, you can assume that reading the input is $O(M \cdot \log M)$. With this assumption, you're trying to distinguish between two algorithms with same time complexity.Try a compressed input like: 0110 1000 1001 0010 
•  » » 7 weeks ago, # ^ |   0 Thanks <3
 » 7 weeks ago, # |   +2 pls let me get a new haircut
 » 7 weeks ago, # |   +33 http://usaco.org/index.php?page=viewproblem2&cpid=946This problem forced $\mathcal O(N^2)$ Prim's by setting $N \leq 7500$ and using an alternative scheme for generating the edge weights to get around input bottleneck. If you take this approach, make sure you pick a better edge weight function because this particular function allowed unintended $\mathcal O(1)$ solutions.
•  » » 7 weeks ago, # ^ |   +8 Thanks so much!
•  » » 7 weeks ago, # ^ |   +24 Unrelated, but how do you solve this in $\mathcal{O}(1)$?
•  » » » 7 weeks ago, # ^ |   +42
 » 7 weeks ago, # |   0 You can drive vertexes into 2 groups, and have small weights inside each one, and big weights from one to another.