I wrote the original post. n^2 seems reasonable to me as well. If you have n pieces, you have to make O(n) connections to solve the puzzle. But to find the

I wrote the original post. n^2 seems reasonable to me as well. If you have n pieces, you have to make O(n) connections to solve the puzzle. But to find the piece that makes each connection, you need to look through O(n) pieces. Multiplying gives O(n^2).