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 ? Insertion – $0(1)$, Deletion – $0(1)$, Maximum – $0(1)$, Minimum – $0(1)$ Insertion – $0(1)$, Deletion – $0(1)$, Maximum – $0(n)$, Minimum – $0(n)$ Insertion – $0(n)$, Deletion – $0(n)$, Maximum – $0(1)$, Minimum – $0(1)$ Insertion – $0(n)$, Deletion – $0(n)$, Maximum – $0(n)$, Minimum – $0(n)$ Algorithms ugcnetjan2017ii algorithms array + – go_editor asked Mar 24, 2020 • recategorized May 24, 2020 go_editor 3.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply junaid ahmad commented Oct 8, 2017 reply Follow Share OPTION C 0 votes 0 votes Please log in or register to add a comment.
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) sarveswara rao v answered Oct 8, 2017 sarveswara rao v comment Share Follow See all 0 reply Please log in or register to add a comment.
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) Debasmita Bhoumik answered Feb 4, 2017 Debasmita Bhoumik comment Share Follow See 1 comment See all 1 1 comment reply Sankaranarayanan P.N commented Jul 26, 2017 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.
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 Rishi yadav answered Oct 10, 2017 Rishi yadav comment Share Follow See all 0 reply Please log in or register to add a comment.
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) Mohit Kumar 6 answered May 7, 2020 • edited May 7, 2020 by Mohit Kumar 6 Mohit Kumar 6 comment Share Follow See all 2 Comments See all 2 2 Comments reply aanchal008 commented May 7, 2020 reply Follow Share but the array is already sorted....deletion still takes O(n) and finding min and max will be O(1) operation. 0 votes 0 votes Mohit Kumar 6 commented May 7, 2020 reply Follow Share actually i miss sorted array part in question now i edit answer 0 votes 0 votes Please log in or register to add a comment.