I read it somewhere that deletion of an element is faster in an unsorted array but I am not sure if that's correct. According to my understanding if we want to delete some particular element then in the case of a sorted array it will take O(log N) time to search it and finally delete it but in the case of the unsorted array it may take in worst case O(N) time to search it linearly before we finally delete it. So how is this possible?

CodePudding user response：

Deleting an element from an array is a O(n) operation if you physically remove that element from the element. That's because all the elements to the right of the deleted element must be shifted. It's only an O(1) operation if the element is at the end of the array so we can pop it.

Now, in an unsorted array you can just swap the found element with the element at the end of the array in O(1) and pop from the end one element, also in constant time.

But in a sorted array, if you want to keep it sorted, you can't do that. You have to physically remove the element to keep the array sorted.

So, to make it clear, you need explicitly say that removing an element from a sorted array and keeping it sorted is O(n). If you don't care about it being sorted, you can remove it in O(1). The searching is logarithmic, so this becomes logarithmic. But you can only do this once. Because after that the array isn't sorted anymore and you can't search for your element in log n time.

CodePudding user response：

Deletion of an element is faster in a sorted array than in an unsorted array.

This is because you can binary search over a sorted array to find the element specified.

An unsorted array has to check every single element one by one (linear search) to find the element to delete.

The delete operation itself is the same time complexity for both.

O(log N) takes less time to execute than O(N).