# Java O(1) space and O(n^2*logn)

• ``````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+1-j), or ,(j, i+1-j));
for (int j = 1; j <= i/2; j++) {
String p1 = "(" + Integer.toString(j) + ",";
String t1 = "((" + Integer.toString(j) + "," + Integer.toString(i+1-j) + "),";
String p2 = "," + Integer.toString(j) + ")";
String t2 = ",(" + Integer.toString(j) + "," + Integer.toString(i+1-j) + "))";
s = s.replace(p1, t1);
s = s.replace(p2, t2);
}
}
return s;
}``````

• Time Complexity is 0 (n*n), not O (nlogn) because run for loop until mid element, doesnt meant logn

• @ruchit_tushar
outer loop is log(n) : "for (int i = 4; i <= n; i *= 2)"

• 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(n2) to me. And here's an experiment, testing n=210 to n=217

``````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 Θ(n2) 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))

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.