Is deletion of an element faster in unsorted array?

Question

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?

Answer 1

Summarising all existing answers,

(And adding a few of my points)

There are two processes we need to consider when we delete an element from any array.

1. Searching for the element in consideration
2. Deletion of that element

Note : In the below explanation, n is the total number of elements in the array.

Searching

• In a sorted array, we can use Binary Search to find the array element to be deleted. The time complexity of Binary Search is O(log n)

• In an unsorted array, we must use Linear Search to find the array element to be deleted. The time complexity of Linear Search is O(n)

Deletion

The removal of an element from any array, is done with a time complexity of O(1).

But the deletion process also includes what must be done after the removal of the element!

• In a sorted array, all the elements to the right of the deleted element must be shifted one index to the left, to fill the space left behind by the deleted element and to maintain sorted order. Therefore, the worst-case time complexity is O(n)

• In an unsorted array, we can fill the space left by the deleted element, with the last element in the array, since the array is unsorted anyway. The time complexity for this process is O(1)

CONCLUSION :

Sorted Array :

• Searching : O(log n)
• Removal : O(n)

Unsorted Array :

• Searching : O(n)
• Removal : O(1)

Answer 2

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).

Answer 3

Deleting an element from an array is a O(n) operation if you physically remove that element from the array. 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.

Answer 4

Sorted array has an order that help us to find given element in O(logN) time. But in unsorted array we have no any order that can help us to find given element so each of the elements of array can be given element, so this enforce us to check all the elements in the array.

Note that, lower bound finding an element in unsorted array is ?(N), because we need check all the elements

Also, because of Array is a static structure, so deletion or insertion is cost-full for us. So for delete in unsorted array you need at the first find it then remove it that has cost O(N).

For deletion in sorted array you can find it in O(logN) and then remove it that has cost O(logN). Note that in this approach, we doesn't shift element of array because this operation is expensive.