Why would a quadratic time algorithm execute faster than a linear time algorithm

Question

Here are two different solutions for finding "Number of subarrays having product less than K", one with runtime O(n) and the other O(n^2). However, the one with O(n^2) finished executing about 4x faster than the one with linear runtime complexity (1s vs 4s). Could someone explain why this is the case, please?

Solution 1 with O(n) runtime:

static long countProductsLessThanK(int[] numbers, int k)
{
    if (k <= 1) { return 0; }

    int prod = 1;
    int count = 0;

    for (int right = 0, left = 0; right < numbers.length; right++) {
        prod *= numbers[right];

        while (prod >= k)
            prod /= numbers[left++];

        count += (right-left)+1;
    }

    return count;
}

Solution 2 with O(n^2) runtime:

static long countProductsLessThanK(int[] numbers, int k) {
    long count = 0;

    for (int i = 0; i < numbers.length; i++) {
        int productSoFar = 1;

        for (int j = i; j < numbers.length; j++) {
            productSoFar *= numbers[j];

            if (productSoFar >= k)
                break;

            count++;
        }
    }

    return count;
}

Sample main program:

public static void main(String[] args) {
    int size = 300000000;
    int[] numbers = new int[size];
    int bound = 1000;
    int k = bound/2;

    for (int i = 0; i < size; i++)
        numbers[i] = (new Random().nextInt(bound)+2);

    long start = System.currentTimeMillis();
    System.out.println(countProductLessThanK(numbers, k));
    System.out.println("O(n) took " + ((System.currentTimeMillis() - start)/1000) + "s");



    start = System.currentTimeMillis();
    System.out.println(countMyWay(numbers, k));
    System.out.println("O(n^2) took " + ((System.currentTimeMillis() - start)/1000) + "s");
}

Edit1:

The array size I chose in my sample test program has 300,000,000 elements.

Edit2:

array size: 300000000:

O(n) took 4152ms

O(n^2) took 1486ms

array size: 100000000:

O(n) took 1505ms

O(n^2) took 480ms

array size: 10000:

O(n) took 2ms

O(n^2) took 0ms

And what happens to performance as you vary the size? For things like 100,000,000 or maybe 10,000 or even just 10. And if you have the memory, even much much larger than 300,000,000. That could be very informative. — Andrew Henle, Jun 26 '18 at 22:00
Solution 2 is not quadratic at all in this context, `k` is a constant and the numbers are at least 2, so the inner loop can only make a constant number of iterations before it *must* take the break. — harold, Jun 26 '18 at 22:05
Could you try running your benchmark with bound=2 and k=500000000? — Tamas Hegedus, Jun 26 '18 at 22:10
Yep. If you count the number of inner loops, you'll have 300,000,000 in one case, and around 450,000,000 in the other. And my guess is that multiplications are faster than divisions — JB Nizet, Jun 26 '18 at 22:13
Microbenchmarking is not a trivial thing to do correctly. You can help yourself by using [JMH](http://openjdk.java.net/projects/code-tools/jmh/). — Nándor Előd Fekete, Jun 26 '18 at 22:24
First of all please see [How do I write a correct micro-benchmark in Java? Ask Question up vote](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). — lexicore, Jun 26 '18 at 23:56

rici · Accepted Answer · 2018-06-26T22:24:49.440

The numbers you are choosing are uniformly distributed in the range [2, 1001], and you're counting subarrays whose products are less than 500. The probability of finding a large subarray is essentially 0; the longest possible subarray whose products is less than 500 has length 8, and there are only nine possible subarrays of that length (all 2s, and the eight arrays of seven 2s and a 3); the probability of hitting one of those is vanishingly small. Half of the array values are already over 500; the probability of finding even a length two subarray at a given starting point is less than one-quarter.

So your theoretically O(n²) algorithm is effectively linear with this test. And your O(n) algorithm requires a division at each point, which is really slow; slower than n multiplications for small values of n.

Its interesting to see when does `On` catches up with `On^2`. If you set `numbers[i] = 2` for all `i` and start increasing `k`, on my computer they are about even at `k ~ 1_000_000` — David Soroko, Jun 26 '18 at 23:06

score 0 · Answer 2 · answered Jun 26 '18 at 22:23

0

In the first one, you're dividing (slow), multiplying and doing multiple sums.

In the second one, the heavier operation is multiplication, and as the first answer says, the algorithm is effectively linear for your tests cases.

answered Jun 26 '18 at 22:23

robertwolfheart

107
4