Is O (1) time complexity for this function?

Question

I was looking through some old notes on algorithms today, and it made me think.

Complexity O(1)means that the execution time of a function is data independent.

So, suppose we have a function to add all elements to an 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_SIZEis the maximum possible size of the array. I know that this code is inefficient, I do not want to discuss this. But +each time an operator is called the same amount of time, and it is not affected by the size of the data.

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

Answer 1

. O (1) , //.

-O- . () "", ().

Answer 2

: " ".

:

• ARRAY_MAX_SIZE , :
  • for
• array.length , :;
  • array[i]
• ARRAY_MAX_SIZE - array.length , :;

,

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

, k_2 k_3. ? O(1). k_2 >> k_3? O(n).

k_2 >> k_3? array[i] , :

Answer 3

- array[i] n . , , i - n . , O(n)? .

, O(1).

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

Answer 4

, O(1). . array.length ARRAY_MAX_SIZE,, array.length , O(1):

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

, , .

This, obviously, suggests that ARRAY_MAX_SIZE- the maximum possible size of the array (as it was defined in the question), and not some other value.