public String findContestMatch(int n) {
if (n < 2) {
return "";
}
String s = "(1,2)";
for (int i = 4; i <= n; i *= 2) {
// Now to the replacement
// (1, > ((1,4),
// ,2) > ,(2,3))
// j = 1 .. i/2, replace "(j," or ",j)"> ((j, i+1j), or ,(j, i+1j));
for (int j = 1; j <= i/2; j++) {
String p1 = "(" + Integer.toString(j) + ",";
String t1 = "((" + Integer.toString(j) + "," + Integer.toString(i+1j) + "),";
String p2 = "," + Integer.toString(j) + ")";
String t2 = ",(" + Integer.toString(j) + "," + Integer.toString(i+1j) + "))";
s = s.replace(p1, t1);
s = s.replace(p2, t2);
}
}
return s;
}
Java O(1) space and O(n^2*logn)



It's really not O(n log n), though. Because your strings get longer and longer, making the string operations more and more expensive. It does look like O(n^{2}) to me. And here's an experiment, testing n=2^{10} to n=2^{17}
public static void main(String[] args) { for (int n = 1 << 10; n <= 1 << 17; n *= 2) { long t0 = System.nanoTime(); new Solution().findContestMatch(n); long t1 = System.nanoTime(); System.out.println(String.format("%7.3f", (t1  t0) / 1e9)); } }
The results:
0.035 0.087 0.274 0.985 4.001 15.985 63.948 260.918
Doubling of n clearly causes roughly a quadrupling in time, agreeing with Θ(n^{2}) complexity.

@StefanPochmann
Yes, you are right, thanks for test it.it is O(n^2 * log(n)) indeed.
For each inner loop:
T(n) = T(n/2) + (n/2) * n = T(n/4) + n^2/2 + n^2/4 = T(1) + n2 * (1/2 + 1/4 + 1/8 + ... ) = n2
outer loop is log(n).
So total O(n^2 * log(n))