How is it possible that O(1) constant time code is slower than O(n) linear time code?

Question

"...It is very possible for O(N) code to run faster than O(1) code for specific inputs. Big O just describes the rate of increase."

According to my understanding:

• O(N) - Time taken for an algorithm to run based on the varying values of input N.
• O(1) - Constant time taken for the algorithm to execute irrespective of the size of the input e.g. int val = arr[10000];

Can someone help me understand based on the author's statement?

1. O(N) code run faster than O(1)?
2. What are the specific inputs the author is alluding to?
3. Rate of increase of what?

Answer 1

O(n) constant time can absolutely be faster than O(1) linear time. The reason is that constant-time operations are totally ignored in Big O, which is a measure of how fast an algorithm's complexity increases as input size n increases, and nothing else. It's a measure of growth rate, not running time.

Here's an example:

int constant(int[] arr) {
    int total = 0;

    for (int i = 0; i < 10000; i++) {
         total += arr[0];
    }

    return total;
}
   
int linear(int[] arr) {
    int total = 0;        

    for (int i = 0; i < arr.length; i++) {
        total += arr[i];
    }

    return total;
}

In this case, constant does a lot of work, but it's fixed work that will always be the same regardless of how large arr is. linear, on the other hand, appears to have few operations, but those operations are dependent on the size of arr.

In other words, as arr increases in length, constant's performance stays the same, but linear's running time increases linearly in proportion to its argument array's size.

Call the two functions with a single-item array like

constant(new int[] {1}); 
linear(new int[] {1});

and it's clear that constant runs slower than linear.

But call them like:

int[] arr = new int[10000000];

constant(arr);
linear(arr);

Which runs slower?

After you've thought about it, run the code given various inputs of n and compare the results.

---

Just to show that this phenomenon of run time != Big O isn't just for constant-time functions, consider:

void exponential(int n) throws InterruptedException {
    for (int i = 0; i < Math.pow(2, n); i++) {
        Thread.sleep(1);
    }
}

void linear(int n) throws InterruptedException {
    for (int i = 0; i < n; i++) {
        Thread.sleep(10);
    }
}

Exercise (using pen and paper): up to which n does exponential run faster than linear?

Answer 2

Consider the following scenario:

Op1) Given an array of length n where n>=10, print the first ten elements twice on the console. --> This is a constant time (O(1)) operation, because for any array of size>=10, it will execute 20 steps.

Op2) Given an array of length n where n>=10, find the largest element in the array. This is a constant time (O(N)) operation, because for any array, it will execute N steps.

Now if the array size is between 10 and 20 (exclusive), Op1 will be slower than Op2. But let's say, we take an array of size>20 (for eg, size =1000), Op1 will still take 20 steps to complete, but Op2 will take 1000 steps to complete.

That's why the big-o notation is about growth(rate of increase) of an algorithm's complexity