0

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;
}
Sazzad Hissain Khan
  • 37,929
  • 33
  • 189
  • 256
  • 5
    Both version appear to search the same number of elements. The second version simply searches two elements each time through the loop. – Galik Jun 09 '17 at 05:04
  • Yes, but the loop will run half. does it reduce the overall complexity? or still it will be considered a O(N) function? I just want to be clear about how it works. Thanks @Galik – Sazzad Hissain Khan Jun 09 '17 at 05:06
  • 2
    They're both O(n). `n/2` is the same as `n` in complexity analysis. In this case it's doubly so since each operation in the `n/2` case is twice as complex as the operations in the `n` case. – Mark Ransom Jun 09 '17 at 05:06
  • No. Take a look at https://stackoverflow.com/questions/22188851/why-is-constant-always-dropped-from-big-o-analysis – pvg Jun 09 '17 at 05:07
  • 4
    The secon loop runs half as many times but does twice as many tests. So one half multiplied by two = 1. The two are exactly the same. – Galik Jun 09 '17 at 05:07
  • If you have to visit every element there is no way to reduce Big O. [Here's an example of a 2D array where various attempts at removing the inner loop are attempted and all have the same result.](https://stackoverflow.com/a/44378975/4581301) – user4581301 Jun 09 '17 at 05:13
  • 2
    Read any competent book on algorithms and you'll get the precise definition of complexity. – Passer By Jun 09 '17 at 05:16

1 Answers1

3

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 c1 such that for every n > n1,

f(n) < c1 n.

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

f(n) < c2 n / 2 = (c2 / 2) n.

Since for any n > max(n1, n2) the inequality holds for c1 = c2 / 2, each of these two implies the other one.

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185