Given an array-based list implementation,
deleting the element at arbitrary position i takes
how long in the average case?
\Theta(n) time\Theta(1) time\Theta(\log n) time\Theta(n \log n) timePosition i could be anywhere in the list
(of n values).
We will need to shift values from position i to
the list end back by one position.
How many we shift depends on the value of i.
On average, it will be half the elements in the list.