Given an array-based list implementation,
inserting a new element to 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.
We will need to shift values from position i to
the list end forward by one position.
How many we shift depends on the value of i.
On average, it will be half the elements in the list.