Search for unsorted array

Question

What will be the smallest and greatest number of comparisons in an unsorted array that can also have duplicate elements?

I understand that finding something in an unsorted array is an O (n) problem. But is this true if the array also contains repeating elements?

I mean duplicate elements that occur more than once in a given array.

Answer 1

So, the idea here is that you need to go through the array from start to finish, because it is unsorted. This means that you are looking at O ​​(n) - a linear traversal of elements. Regardless of whether the one you are looking for is at position 0, position 8 or position n-1, you need to go through the array to find it.

Now, if there are duplicates in the array, the only difference is that you can find more than one instance of the value. If you are looking for all of them or just the first one, this is still an O (n) situation. Duplicates do not change complexity.

The best case is that you find it (assuming you only need to find it) in the first comparison.

In the worst case, there are no duplicates for a given value, and this is the last one you check is the nth comparison.

, n , .

Answer 2

O(n) , . - .

: 1, 1, 1, 1, ..., 1, 1, 2. 2 n , , . 1, , , , , " , , . O(n).

. , " " , . , , , , , .

, .

Answer 3

, 2n

for (int i=0; i<n; i++)
    if (a[i]==ele)
        break
    else
        continue;

, (i<n) (a[i]==ele) n . 2n . , i<n, , .

Answer 4

, , , O (n), , , .. , O (n) O (n).

. , 10 , , , 10 ( ), n, .

Answer 5

?

, 1 n . , , , n-1.

, - - O (n). , ?

, O (n).

, , . , , O (n). Big-O - , , . n O, .

Answer 6

Like everyone else, I agree to an unsorted array that does not contain duplicates, an exhaustive linear search will be O (n).

If duplicates are allowed, the algorithm remains only O (n) under the assumption that the probability of duplication of any element is evenly distributed.

If there is another probability density function that describes the distribution of repeating elements, then the search algorithm is likely to be less than O (n) depending on the probability density function.