Given a linked list implementation, inserting a new element to arbitrary position i takes how long in the average case?

\Theta(i) time
  • \Theta(n) time
  • \Theta(1) time
  • \Theta(\log n) time
  • \Theta(n \log n) time

We can't insert until we reach the proper position.

How long does it take to reach position i in a linked list?

Once we get there, it takes only a couple of assignments to put the new node in place.