Consider the following implementation of a queue (code [here](rec-code/twoListQueue.ml)):
```
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, List.tl 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/test.ml)):
```
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:
![plot of running time, looks quadratic](times.png)
It seems to take $O($`n`$^2)$ time. Explain the discrepancy.