Question on sorted array and time complexity

Question

Which of the following operations can be performed in O(log n) time or faster on a sorted array A? (n denotes the size of array)

1) Search(A, x)

2) Find-Minimum(A)

3) Delete(A, x)

Choose the correct option:

A.) 1 & 3

B.) 1 & 2

C.) 2 & 3

D.) All of them

I chose option B but the book says option D is right. Please provide an explanation.

Comments

@ joshi_nitish minimum takes O(1) ??

---

yes, if you delete last element of an array.

---

why are you swapping after delete?you can put any symbol like $ at palace of deleting.question is asking for delete element not saving array after that ?

according to me all are true.

Answer 1

Search(A, x): Use binary search. Time is O(log n)

Find-Minimum(A): Can be performed in O(1) time, as the first or last element is minimum depending on whether the array is sorted in ascending or descending order respectively.

Delete(A, x): Search x + move other elements after x = O(log n) + O(n) = O(n)

Hence (B) is correct.

Comments

I'm confused what delete means in this case. I mean, considering the answer in the book is correct, then we can implement delete in O(log n) for searching the element and setting the value at the index to some predefined invalid value in O(1). for example, something like Math.INFINITY, And modify all other methods to ignore whenever this Math.INFINITY shows up, as if the element didn't exist.

Answer 2

In general Insertion and deletion in a BST takes O(n) and search takes O(logn), but in a special case DELETION takes O(1) when we have to delete the last element.

Finding minimum is giving the element present at index 0, so it takes O(1).

Comments

Not always o(1)