Is there an algorithm faster than O(quadratic)?


  • 0
    X

    I wondering if there is an algorithm that is faster than O(quadratic).

    If so, please paste the link to such solution.

    Thanks!


  • 0
    S

    Think about it like this. What is the maximum possible size of a solution set? It's O(n^2). Therefore, to explore all those possible solution states it would take at least O(n^2) time.


  • 0
    X

    Well, what I am thinking is that as long as we have looped through all elements (i.e., have the full information about this array), we should be able to get the result. That's why I think there should be a O(N) solution. Can you explain further on why the solution set is O(quadratic)? Thanks!


  • 1
    S

    @xinxi531 Try to come up with an array that would have the most number of solutions...It would probably look something like this:

    [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4. 5]

    Which leads to a set of solutions like so:
    [-5, 5, 0], [-5, 4, 1], [-5, 3, 2]
    [-4, 5, -1], [-4, 4, 0], [-4, 3, 1]
    [-3, -2, 5], [-3, -1, 4],[-3, 0, 3], [-3, 1, 2]
    [-2,-1,3], [-2, 0, 2]
    [-1,0,1]

    This type of solution pattern, if extend to -N to N for very large N can be shown to grow at O(N^2). I believe it is similar to the concept of the sum of the first n numbers = n(n+1)/2, which is quadratic.

    Out of curiosity, I plotted the size of solution set if you kept growing the example above by another pair of positive and negative values, and the solution set grew from 13 to 18 to 25 to 32:

    ThreeSum underTest = new ThreeSum();
    
    @Test
    public void threeSum() throws Exception {
        int[] arr = new int[]{-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5};
        assertEquals(13, underTest.threeSum(arr).size());
        arr = new int[]{-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6};
        assertEquals(18, underTest.threeSum(arr).size());
        arr = new int[]{-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7};
        assertEquals(25, underTest.threeSum(arr).size());
        arr = new int[]{-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8};
        assertEquals(32, underTest.threeSum(arr).size());
    }
    

    In conclusion, to discover O(N^2) solutions (picture printing them out) would have to be done in O(N^2) time. You cannot do that in O(N) time. It'd be the equivalent of saying print the numbers 1 to 100 in 10 operations. You'd need 100 operations at minimum to do it. I hope I was clear?


  • 0
    X

    @sharkhuh That makes much more sense. Thank you for your detailed reply!


Log in to reply
 

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