CODEWITHSUNDEEP
algorithmtime-complexity
user4376896
user4376896

Reputation:

Search operation complexity

What would be the complexity of a search operation in an unsorted array that allows duplicates. My guesses were O(N) since it allows duplicates, the whole array needs to be searched. But I'm new to algorithm complexity and I cannot be sure about my answer, can you please confirm if I'm correct.

Upvotes: 1

Views: 55

Answers (3)

Jordi Vermeulen
Jordi Vermeulen

Reputation: 1198

It is O(n) because in the worst case you still need to look at every element.

Upvotes: 0

Pétur Ingi Egilsson
Pétur Ingi Egilsson

Reputation: 4493

Searching for elements within an unordered array would indeed be O(N) as no heuristic can speed up the search.

Upvotes: 0

maniek
maniek

Reputation: 7307

Since the array is unsorted, you have to look at half of the array on average to find the element you are searching for. Therefore, complexity is linear - O(N). Duplicates or no duplicates, the same complexity.

Upvotes: 1

Related Questions