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


  • 0
    A
    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;
    }

  • 0

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


  • 0
    A

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


  • 0

    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.


  • 0
    A

    @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))


Log in to reply
 

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