2,533 views

Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array ?

1. Insertion – $0(1)$, Deletion – $0(1)$, Maximum – $0(1)$, Minimum – $0(1)$
2. Insertion – $0(1)$, Deletion – $0(1)$, Maximum – $0(n)$, Minimum – $0(n)$
3. Insertion – $0(n)$, Deletion – $0(n)$, Maximum – $0(1)$, Minimum – $0(1)$
4. Insertion –  $0(n)$, Deletion – $0(n)$, Maximum – $0(n)$, Minimum – $0(n)$

### 1 comment

OPTION  C

bcz

when u do the insertion or deletion u may have to shift the entire list ( of size n ) a position ahead making TC = O(n).

the first element will be the min and the last element will be the maximum for non-decreasing order TC= O(1)
option 3

array is sorted.

so in worst case, last item insert Insertion-O(n),

in worst case, last item delete Deletion-O(n),

maximum and minimum is always at end , we know the positions.

Maximum-O(1), Minimum-O(1)

### 1 comment

for inserting/deleting in any position in array we need to shift the  elements accordingl. this shift operation is the costlier one. the anwer you pointed out is correct, but the reason is not exact
Time complexity in big O notation
Algorithm Space Average Worst Case O(n) O(n) O(log n) O(log n) O(n) O(n) O(n) O(n)

reference : https://en.wikipedia.org/wiki/Sorted_array

ANS should be  Option C

in array random access possible because array is sorted given in question

insert  and deletion will take   0(n) for insertion we have to find correct position to insert element in sorted order and for deletion we have to search element for deletion.

But finding max or min element in sorted array will take O(1) time because  for minimum it will be first element of array or for  maximum element it should be last element of array( let  array in increasing order)

but the array is already sorted....deletion still takes O(n) and finding min and max will be O(1) operation.
actually i miss sorted array  part in question now i edit answer