Time Complexity in Sorted Array

Question

Given an sorted array in descending order, what will be the time complexity to delete the minimum element from this array?

================================================

My take the minimum element will be at last position so O(n) to find it? or should I apply Binary search since array is sorted or simply O(1) to reach at the end?

• Carcigenicate: If the array is sorted, you shouldn't have to search at all. If you know the array length, the smallest element will be at index length - 1.
• Geeklovenerds: So, Time Complexity is O(1)?
• Carcigenicate: Yes. If it was a linked list, it would be O(n) since you'd have to iterate the entire list to get to the last element. That isn't necessary for an array though.
• Carcigenicate: Actually, whoops, it's O(1) to find the smallest element, but deletion would be O(n) if a copy of the array is made. It depends if you're making a smaller copy of the array, or just leaving the last slot null. I think "delete" needs to be defined here.
• Geeklovenerds: If I'm only simply deleting and not making any copy of the original array?

Answer 1

It really depends on what you mean "delete from the array." You have an array, sorted in descending order, and you want to delete the minimum element.

Let's say that the array is [5, 4, 3, 2, 1]. You know how large the array is, so finding the minimum element is O(1). You just index a[a.length-1].

But what does it mean to delete the last element? You can easily replace the value there with a sentinel value to say that the position is no longer used, but then the next time you tried to get the minimal element, you'd have to visit a[a.length-1], and then do a reverse scan to find the first used element. That approaches O(n) as you remove more items.

Or do you keep a counter that tells you how many values in the array are actually used? So you'd have a variable, count, to tell you which is the last element. And when you wanted to get the minimal element you'd have:

smallest = a[count];
count = count-1;

That's still O(1), but it leaves unused items in the array.

But if you want to ensure that the array length always reflects the number of items are in it, then you have to re-allocate the array to be smaller. That is O(n).

So the answer to your question is "It depends."

Answer 2

Since the array is sorted in descending order, the minimum element will be always guaranteed to be in last location of array, assuming there are no duplicates in the array. Deletion can be done in O(1).

If you need to do a series of deletions on the array, then you may want to adjust the deleted indices and point to the correct end location of the array. This can be done in constant time.

Hence to sum it up, the total time complexity would be O(1)

• Jim Mischel: It's in descending order, so the minimum element is at the end of the array. If it was at the start of the array, deletion would be O(n).