Which of the following is true for computation time in insertion, deletion and…
2017
Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array ?
- A.
Insertion – 0(1), Deletion – 0(1), Maximum – 0(1), Minimum – 0(l)
- B.
Insertion – 0(1), Deletion – 0(1), Maximum – 0(n), Minimum – 0(n)
- C.
Insertion – 0(n), Deletion – 0(n), Maximum – 0(1), Minimum – 0(1)
- D.
Insertion – 0(n), Deletion – 0(n), Maximum – 0(n), Minimum – 0(n)
Attempted by 565 students.
Show answer & explanation
Correct answer: C
Answer: Insertion – O(n), Deletion – O(n), Maximum – O(1), Minimum – O(1)
Explanation:
Insertion: You must place the new element at the correct sorted position. Finding the position can be done in O(log n) using binary search, but after finding it you usually need to shift all following elements to make room. Shifting elements takes O(n) in the worst case, so overall insertion is O(n).
Deletion: Removing an element requires shifting subsequent elements to fill the gap. Even if you locate the element quickly (for example, with binary search), the shifting step is O(n) in the worst case, so deletion is O(n).
Finding maximum and minimum: In a sorted array the minimum and maximum are at the ends (for ascending order, minimum at index 0 and maximum at index n-1). Accessing these positions is direct and takes O(1).
Therefore, the correct time complexities for a sorted array are insertion O(n), deletion O(n), maximum O(1), and minimum O(1).