4,551 views
7 votes
7 votes

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.

2 Answers

5 votes
5 votes
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.
–1 votes
–1 votes
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).
Answer:

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,090 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
8 votes
8 votes
2 answers
2