Time complexity for Search and Insert operation in sorted and unsorted arrays that includes duplicat
- by iecut
1-)For sorted array I have used Binary Search.
We know that the worst case complexity for SEARCH operation in sorted array is O(lg N), if we use Binary Search, where N are the number of items in an array.
What is the worst case complexity for the search operation in the array that includes duplicate values, using binary search??
Will it be the be the same O(lg N)?? Please correct me if I am wrong!!
Also what is the worst case for INSERT operation in sorted array using binary search??
My guess is O(N).... is that right??
2-) For unsorted array I have used Linear search.
Now we have an unsorted array that also accepts duplicate element/values.
What are the best worst case complexity for both SEARCH and INSERT operation.
I think that we can use linear search that will give us O(N) worst case time for both search
and delete operations.
Can we do better than this for unsorted array and does the complexity changes if we accepts duplicates in the array.
