Past exam of the computer science course of the University of Oxford / 2015 / Advanced data structures and algorithms / 1

The accounting method assigns each operation a charge, its amortized cost, that can differ from its actual cost. Cheap operations save the excess charge as credits associated with the data structure or its entries. An expensive operation spends these previously saved credits. The essential invariant is that the credit balance never becomes negative.

If the initial balance is zero, operation $i$ has actual cost $c_i$, charge ${\hat{c}}_i$, and leaves balance $B_i$, thenThus a nonnegative credit balance makes the total charge an upper bound on the total actual cost for every operation sequence. In particular, a constant time charge proves a linear time total. The argument is a deterministic amortized analysis; it requires no probability distribution on the operations. A nonzero initial balance must be included as an additive term in the bound.

Yes: starting from zero, $n$ increments of the decimal counter cost $\Theta (n)$ digit changes, uniformly in the number $k$ of digits. An increment changes the trailing digits equal to $9$ into $0$ and increases the next digit. Number digits from $0$ at the least significant end. Digit $i$ changes once every $10^i$ increments, so the exact number of changes isHere the floor function counts carries reaching each position, and the last equality sums a geometric series. Since digit $0$ changes on every increment, $C_{10}(n,k)\ge n$ for $k\ge 1$. The loop tests and carry handling add only a constant amount per changed digit and per operation, giving the same time complexity.

An accounting method explanation is also possible. Charge two credits for each change of digit $0$: one pays for that change and one joins a common bank. For $n$ increments the higher digits change at most $n/9$ times, so their costs can be covered from that bank; the displayed prefix bound ensures that it never goes negative.

The formula allows wraparound modulo $10^k$; alternatively, restrict to increments before overflow. Initializing the array itself costs $\Theta (k)$ if that is counted separately. If the initial digits are arbitrary, the number of changes at position $i$ is at most $\lceil n/10^i\rceil$, giving $O(n+k)$ in Big O notation. Starting with all digits equal to $9$ makes the first increment cost $k$, so the initial-state convention matters.

For an initially zero binary counter, bit $i$ changes precisely on increments whose indices are divisible by $2^i$. Weighting each such change by $2^i$ gives the exact totalFor $n\ge 1$ and $k\ge 1$, put $r=\min \{k,1+\lfloor {\log }_{2}n\rfloor \}$. All summands with $i\ge r$ vanish; each of the other summands is at most $n$. ThereforeThis is sharper than simply charging $n$ for each of all $k$ positions when $n$ is small. To show that the order is best possible, use $\lfloor x\rfloor \ge x/2$ for $x\ge 1$. For every $0\le i<r$,Thus the asymptotic analysis gives a tight bound. If wraparound is excluded, $n<2^k$, and this becomes $\Theta (n(1+{\log }_{2}n))$, often written $\Theta (n\log n)$ for $n\ge 2$. If wraparound is allowed and $n\ge 2^k$, it becomes $\Theta (nk)$. For $n=0$, the cost is zero.

For completeness, the same conclusion cannot be asserted uniformly over arbitrary initial binary counter states. An initial value $2^k-1$ makes the first increment change every bit, costing $2^k-1$. A general upper bound follows by replacing each floor function in the count by a ceiling function:To see the second inequality, split at $r$: for $i<r$, use $\lceil n/2^i\rceil \le n/2^i+1$, and for $i\ge r$, use $\lceil n/2^i\rceil =1$. For $n\ge 1$ the worst initial-state cost is consequently $\Theta (nr+2^k)$. This qualification separates initialization from the usual amortized analysis starting at zero.

Use two permanent stacks, $F$ and $B$, and one temporary stack, $T$. At operation boundaries $T$ is empty. Maintain the representation invariant that the deque, read from front to back, is the top-to-bottom contents of $F$ followed by the bottom-to-top contents of $B$. Thus the tops of $F$ and $B$ are the two accessible ends. Maintain their sizes using two counters, requiring only $O(1)$ additional storage in Big O notation.

Adding at the front pushes onto $F$; adding at the back pushes onto $B$. Removing at an end whose permanent stack is nonempty simply pops that stack. If both permanent stacks are empty, report an empty deque.

Suppose a front removal finds $F$ empty and $B$ contains $m>0$ elements. Rebalance as follows:

The parked elements are the back half of the deque; the unparked elements are the front half. Moving the front half onto $F$ reverses their stack order and exposes the correct front element. Parking and restoring the back half reverses it twice, preserving its original order in $B$. The temporary stack is empty again. For a back removal with $B$ empty, exchange the roles of $F$ and $B$ throughout. Rebalance approximately half the elements, so both ends retain accessible elements after a large transfer.

For the amortized analysis, count each push or pop as one unit and use the potential method withInitially the deque is empty, so $\Phi =0$, and $\Phi$ is always nonnegative. An ordinary insertion or removal costs one unit and changes the size difference by at most one, giving amortized cost at most $4$.

For a rebalancing removal, let $h=\lfloor m/2\rfloor$. The parked half makes two transfers per element and the other half makes one; each transfer is a pop and a push. Including the final removal, the actual cost isBefore rebalancing the absolute size difference is $m$. Immediately after the split it is at most $1$, and after the removal it is at most $2$. HenceSize tests and counter updates change only these constants. Summing the amortized costs and using nonnegative final potential proves $O(1)$ amortized running time for all four operations, with three stacks and $O(1)$ additional storage. An individual rebalancing operation can still take linear time in the current size.