Is time complexity for this function is O(1)?

Question

I was reviewing some old notes on algorithms today, and this got me thinking.

Complexity O(1) means execution time for function is independent on data.

So let's suppose we have a function to add all elements in array.

int add(int[] array){
    int sum =0;
    for (int i=0;i<ARRAY_MAX_SIZE;i++){
      sum= sum + (i<array.length?array[i]:0);
    }
    return sum;
}

where ARRAY_MAX_SIZE is maximum possible size of array. I know this code is not efficient i don't want to discuss this. But operator + is called same amount time each time and it is not affected by size of data.

Does that means complexity of this function is O(1)?

Answer 1

Yes. O(1) means constant time, not fast/efficient/optimal.

Big-O complexity ignores the complexity of constant steps. A division (slow) is just as "complex" as an increment (fast).

Answer 2

The actual answer is "it depends".

There are two different sets of things happening here:

• ARRAY_MAX_SIZE times, you:
  • Increment and test a for loop
  • add to the total
• array.length times, you:;
  • access array[i]
• ARRAY_MAX_SIZE - array.length times, you:;
  • load the constant zero

So the total runtime is

t = k_1 * ARRAY_MAX_SIZE +
    k_2 * n +
    k_3 * (ARRAY_MAX_SIZE - n)

So you look at how k_2 and k_3 compare. Are they basically equal? Then it's O(1). Is k_2 >> k_3? Then it's O(n).

Why might k_2 >> k_3? Because array[i] is accessing memory, and memory is comparatively very slow: