Is deletion of an element faster in unsorted array?

Solution 1:

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

Solution 2:

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.

Solution 3:

Summarising the two existing answers,

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)