Consider the following implementation of a queue (code [here](rec-code/ ``` module Queue = struct (** * Abstraction function: the value { * incoming = [a(n); a(n-1); ...; a(j)]; * outgoing = [a(1); a(2); ...; a(j-1)]; * } * represents the queue * [a(1); a(2); ....; a(j-1); a(j); ...; a(n)] * * In other words, outgoing contains the front of the queue in normal order, * and incoming contains the back of the queue in reverse order. * * Rep invariant: none. *) type 'a t = { incoming : 'a list; outgoing : 'a list; } (** The empty queue *) let empty = { incoming = []; outgoing = []; } (** return the number of elements that have been pushed but not popped *) let size q = List.length q.incoming + List.length q.outgoing (** push an element on the back of the queue *) let push q v = {q with incoming = v::q.incoming} (** * [pop q] returns [Some (v,q')] where v is the front of q and q' is the rest * of q. Returns [None] if the queue is empty. *) let pop q = match q with | {incoming = []; outgoing = []} -> None | {incoming = vs; outgoing = h::tl} -> Some (h, {incoming=vs; outgoing=tl}) | {incoming = vs; outgoing = []} -> let out = List.rev vs in let (h,tl) = List.hd out, out in Some (h, {incoming=[]; outgoing=tl}) end ``` **Exercise**: What is the asymptotic worst-case running time of `push q v` in terms of $n =$`size q`? **Exercise**: What is the asymptotic worst-case running time of `pop q` in terms of $n =$`size q`? You may assume that `List.rev l` runs in time $O($`List.length l`$)$, and `hd` and `tl` run in constant time. **Exercise**: Use the aggregate method to argue that a sequence of $k$ `push` and `pop` operations will take $O(k)$ time. **Exercise**: Use the banker's method to show that the amortized running time of `push` and `pop` are both $O(1)$. **Exercise**: Use the physicist's method to show that the amortized running time of `push` and `pop` are both $O(1)$. **Exercise**: Consider the following program (code [here](rec-code/ ``` let test n = (** push k numbers onto q, return the resulting queue *) let rec push_many (q:int Queue.t) (k:int) = if k = 0 then q else push_many (Queue.push q k) (k-1) in (** pop k times from q, return () *) let rec pop_many q k = if k = 0 then () else match Queue.pop q with | None -> () | Some (_, q') -> pop_many q (k-1) in let q = push_many Queue.empty n in pop_many q n ``` A student argues that since `test n` makes `n` calls to `push` followed by `n` calls to `pop`, and since both `push` and `pop` take $O(1)$ time, that `test n` should take $O($`n`$)$ time. However, the student measures the running time of the program and sees the following behavior: <center> ![plot of running time, looks quadratic](times.png) </center> It seems to take $O($`n`$^2)$ time. Explain the discrepancy.