What is the Complexity of Find() Function

Question

I have two versions of find function, both of which search an integer value in an array and return its position if exists. Function find1() will search up to N elements in worst case on the other hand find2() function will search up to N/2 elements in worst case. Does it mean find2() functions complexity is reduced into O(N/2)?

I assume the array arr contains non-duplicating values.

Function: find1()

int find1(int value){
    for (int i = 0; i < N; i++){
        if (arr[i] == value){
            return i;
        }
    }
    return -1;
}

Function: find2()

int find2(int value){
    for (int i = 0, j = N - 1; i <= j; i++, j--){
        if (arr[i] == value){
            return i;
        }
        if (arr[j] == value){
            return j;
        }
    }
    return -1;
}

Answer 1

To begin with, the first version does in the worst case n iterations, and, in each iteration, does a constant number of operations. The second version does in the worst case n / 2 iterations, and, in each iteration, also does a constant number of operations, but a larger constant. Thus, there is no reason to think that the first is O(n) and the second is O(n / 2).

In any case, O(n) = O(n / 2). By the definition of O, O(n) means that there is a constant c₁ such that for every n > n₁,

f(n) < c₁ n.

Similarly, O(n / 2) means that there is a constant c₂ such that for every n > n₂,

f(n) < c₂ n / 2 = (c₂ / 2) n.

Since for any n > max(n₁, n₂) the inequality holds for c₁ = c₂ / 2, each of these two implies the other one.