It is O(n) in the worst case. Run a time complexity analysis of your code for an array with the same element repeated.

In fact it can be proved that worst case complexity cannot be better than O(n). Simply consider the case of an array with all indices set to 1 except for one which is set to 0. Now, this 0 could be anywhere in the array, and you can't possibly know where it is without looking at each possible index.

By the way, the part where you check for the size of the array is unnecessary.