Given a linked list implementation, deleting the element at arbitrary position i takes how long in the average case?

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

You cannot delete a node until you get to it.

Starting from the front, how long does it take to get to the ith node?

Once you do reach the node, then you can remove it in constant time.