Suppose we use a linked list to implement a slight variation of a dictionary
. Assuming no duplicate elements are provided, we can just insert elements at the beginning of the list. Assume the peculiar situation that the client may perform any number of insert operations but will only ever perform at most one lookup operation.
What will the worst-case amortized running-time of the lookup and insert operations performed on this data structure be?