It can certainly not be any lower than n log n, because one is trying to communicate here through the match/no-match yes/no answers the identity of a bijection, one of n! possible outcomes. Even if we were able to use any set of questions, rather than the set of tile-matching questions we are restricted to, this cannot be done in less than log(n!) bits of information, or log(n!) answers, which gives the desired lower bound.
In order to show that it is not higher, we construct a specific S and a specific strategy that attains O(n log n) over S.
We begin by describing S. We construct S over another set of puzzles, S'. Let S' be any set of puzzles without self-symmetries with an unbounded puzzle size.
We will now "expand" each element of S' into a new graph, and these expanded graphs will be the elements of S. The expansion process is as follows:
Let k be the original puzzle size, and let its vertices be R1 through Rk. We add to the graph another 2k-1 vertices, which we label L1 through L2k-1. The L vertices are not connected to each other, but they are connected to the R vertices as follows. Each Li is connected exactly to those Rj for which the j'th position in the binary representation of i is 1.
The resulting S is clearly unbounded in its size, as the size of each new element is n=k+2k-1. Let us prove that each of its elements lacks self-symmetries: first, note that each R vertex connects to at least 2k-1 vertices in the graph, whereas L elements connect to at most k. With k having to be at least 6 due to the original graph lacking self-symmetries, these two groups are clearly distinguishable. Within the R set, the vertices can be labelled uniquely, because their subgraph is taken from S', which we assumed contains no self-symmetries. Lastly, once the label of each R-vertex is known, the identity of each L vertex can simply be read out in binary form based on which R vertices it is connected to.
Let us now describe an algorithm that solves this jigsaw puzzle in O(n log n) tile-match comparisons.
1: Let T be the original set of tiles.
2: Bag←T.
3: While Bag≠Ø:
4: Pick x arbitrarily from Bag.
5: Try to match x with every tile it hasn't been compared with, yet.
6: Let N be the set of all of x's neighbours.
7: If |N|≤k: // x is in L
8: NewR←N.
9: Else: // x is in R
10: NewR←{x}.
11: For each r in NewR:
12: Try to match r with every tile it hasn't been compared with, yet.
13: Remove r and all its neighbours from Bag.
Let us analyse this algorithm. First, note that each element in L has at least one neighbour, so NewR is never empty. For this reason, we know that Bag shrinks by at least one element in every iteration through the loop of step 3. So, we know that the algorithm terminates.
Next, we know that for every r found -- that is, for every new element found in R -- we remove at step 13 all elements in Bag that are at distance at most 1 from it in the connectivity graph. Because the elements of NewR are all at distance at most 1 from x (an element picked from Bag) whether NewR was populated at step 8 or step 10, we know that no element in NewR can ever be a previously-used r value. The r values all belong to R and R is of size k=O(log n), so the loop at step 11 can repeat in total at most this many times. Because NewR is never empty, this number of iterations is at least as large as the number of repetitions through the loop of step 3. In total, we see that the number of times the algorithm passes through both step 5 and step 12 is O(log n). At each of these steps, it makes at most n comparisons, for a total of O(n log n), as required.
Finally, note that if Bag is empty then, in particular, all elements have been removed from L, which can only be done if they appeared as neighbours of values of r. We claim that this means that every value in R must have appeared as an r value. To see this, note that for any Ri the element L2i-1 is an element that connects only to it. Its removal from Bag indicates that Ri appeared as a value of r. So, we know that all elements of R have been used as r values, and therefore every match between any element of R and any other element has been tried. In our puzzle graph, there are no edges between elements of L, so this indicates that every edge in the graph has already been found. Because we know that the graph has no self-symmetries, we know from this that the puzzle has been solved.
Q.E.D.