2.2 2.3 We now determine the runtime complexity of the enq and (leg operations. Let k be the total number of elements in the queue. What is the worst-case runtime complexity of each of the following queue opera- tions based on the description of the data structure implementation given above? Write ONE sentence that explains each answer. enq : O( ), because deq: O( ), because Using amortized analysis, we can show that the worst-case complexity of a valid sequence of 11 enqueue / dequeue operations starting from an empty queue is 001). This means that the amortized cost per operation is 0(1), even though the worst- case cost of an individual operation may not be constant. Here, a valid sequence of queue operations must start with the empty queue, each operation must be either an enq or a deq , and you must have enough tokens. Assume that push and pop each consume one token (and emptiness tests are free). How many tokens should be charged to enqueue an element? How many to dequeue an element? Give the smallest possible number of tokens so that the amortized cost is 0(1). Justify each answer by briey stating for what purpose of each token is used (you may not need all lines), Cost of enq : token(s), to be used as follows: 1 token to 1 token to 1 token to 1 token to Cost of deq : token(s), to be used as follows: 1 token to 1 token to 1 token to 1 token to