in Algorithms recategorized
2,533 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)$
in Algorithms recategorized
2.5k views

1 comment

OPTION  C
0
0

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)

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
0
0
0 votes
0 votes
Time complexity in big O notation
Algorithm   Average Worst Case
Space   O(n) O(n)
Search   O(log n) O(log n)
Insert   O(n) O(n)
Delete   O(n) O(n)

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

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

2 Comments

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

Related questions