What is the average time complexity of deleting an element from a random position in an array while keeping the remaining elements contiguous?
Correct answer B. O(n)
Explanation
After removing an element, every element to its right must shift one place left to close the gap. On average about half the array moves, which is still proportional to n, so the cost is O(n). Constant time is only possible when deleting the last element, or when order does not matter and you overwrite the deleted slot with the last element.
Answer checked How we write and check questions
Discussion