recategorized
3,607 views
0 votes
0 votes

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)$
recategorized

5 Answers

2 votes
2 votes
The answer is 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)
0 votes
0 votes
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)
0 votes
0 votes
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)
edited by
Answer:

Related questions

0 votes
0 votes
4 answers
3
go_editor asked Mar 24, 2020
989 views
Match the following :$\begin{array}{llll} & \textbf{List – I} & {} & \textbf{List – II} \\ \text{a.} & \text{Absurd} & \text{i.} & \text{Clearly impossible being con...