CODEWITHSUNDEEP
arraysdata-structures
Geeklovenerds
Geeklovenerds

Reputation: 327

Time Complexity in Sorted Array

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?

Upvotes: 0

Views: 2253

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 133975

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

Upvotes: 3

tourist
tourist

Reputation: 4333

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)

Upvotes: 0

Related Questions