Searching an unsorted array

Question

What would be the smallest and largest number of comparisons in an unsorted array that could have duplicate elements as well ?

I understand that finding anything in an unsorted array is a O(n) problem. But, is this true if the array contains duplicate elements as well ?

By duplicate elements I mean, elements that occur more than once in the given array.

Answer 1

So the idea here is that you've got to walk the array from front to end because it is unsorted. That means you're looking at O(n) - a linear traversal of the elements. Regardless of whether the one you are searching for is at position 0, position 8, or position n-1, you've got to walk the array to find it.

Now, if there are possibly duplicates in the array, the only difference is that you may find more than one instance of the value. If you are looking for all of them or just the first one, it is still a O(n) situation. The duplicates don't change the complexity.

Best case - you find it (assuming you only need to find one) on the first comparison.

Worst case - there are no duplicates for the given value and it is the last one you check - the nth comparison.

If you had to find ALL of the duplicates, it is always going to be n comparisons, because you've got to visit each element in the unsorted array.

Answer 2

The O(n) time is true even if there are duplicate elements. You should familiarize yourself with big-oh notation.

In the worst case, consider this array: 1, 1, 1, 1, ..., 1, 1, 2. Searching for 2 will take exactly n comparisons if you start from the first element, so having duplicates didn't help at all. If you were to search for 1, you'd find it in a single comparison, but there are inputs of distinct elements for which you can also find an element in a single comparison if you're lucky, so having duplicates really doesn't mean much, except that you're more likely to get lucky and find your target element in fewer steps. It will still be O(n) however.

There are almost always best cases and worst cases. The practical performance of most algorithms always depends on the given input, big-oh notation just gives you a vague idea of how the algorithm will perform. This isn't to say that asymptotic notation is useless, just that it's not always entirely accurate because there are underlying constants involved that do make a difference in practice.

If in doubt about performance, run your own benchmarks.