$\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS

Question

The following comes from section Dynamic Tables, Introduction to Algorithms by Cormen. et. al.

---

In the following pseudocode, we assume that $T$ is an object representing the table. The field $table[T]$ contains a pointer to the block of storage representing the table. The field $num[T]$ contains the number of items in the table, and the field $size[T]$ is the total number of slots in the table. Initially, the table is empty : $num[T] = size[T] = 0$.

$\text{Table-Insert(T,x)}$

$1\quad \text{if $size[T]=0$}$

$2\quad\quad \text{then allocate $table[T]$ with $1$ slot}$

$3\quad\quad size[T] \leftarrow 1$

$4\quad\text{if } num[T] =size[T]$

$5\quad\quad\text{then allocate $new{\text{-}}table$ with $2 \times size[T]$ slots}$

$6\quad\quad\quad\text{insert all items in $table[T]$ into $new{\text{-}}table$}$

$7\quad\quad\quad\text{free $table[T]$}$

$8\quad\quad\quad table[T] \leftarrow new{\text{-}}table$

$9\quad\quad\quad size[T] \leftarrow 2 \times size[T]$

$10\quad \text{insert $x$ into $table[T]$}$

$11\quad num[T] \leftarrow num[T] + 1$

For the amortized analysis for the a sequence of $n$ $\text{Table-Insert}$ the potential function which they choose is as follows,

$$\Phi(T) = 2 \times num[T]-size[T]$$

To analyze the amortized cost of the $i$th $\text{Table-Insert}$ operation, we let $num_i$ denote the number of items stored in the table after the $i$ th operation, $size_i$ denote the total size of the table after the $i$ th operation, and $\Phi_i$ denote the potential after the $i$th operation.

Initially, we have $num_0 = 0, size_0 = 0$, and $\Phi_0 = 0$.

If the $i$ th Table-Insert operation does not trigger an expansion, then we have $size_i = size_{i-i}$ and $num_i=num_{i-1}+1$, the amortized cost of the operation is $\widehat{c_i}$ is the amortized cost and $c_i$ is the total cost.

$$\widehat{c_i}=c_i+\Phi_i- \Phi_{i-1} = 3 \text{ (details not shown)}$$

If the $i$ th operation does trigger an expansion, then we have $size_i = 2 \times size_{i-1}$ and $size_{i-1} = num_{i-1} = num_i —1$,so again,

$$\widehat{c_i}=c_i+\Phi_i- \Phi_{i-1} = 3 \text{ (details not shown)}$$

---

Now the problem is that they do not make calculations for $\widehat{c_1}$, the situation for the first insertion of an element in the table (line 1,2,3,10,11 of code only gets executed).

In that situation, the cost $c_1=1$, $\Phi_0=0$ and $num_1=size_1=1 \implies \Phi_1 = 2 \times 1-1 =1$

We see that $\Phi_1=1 \tag 1$

So, $$\widehat{c_1}=c_1+\Phi_1-\Phi_0=2$$

But the text says that the amortized cost is $3$, (I feel they should have said the amortized cost is at most $3$, from what I can understand)

Moreover in the plot below,

The text represents graphically the $\Phi_1=2$ which sort of contradicts $(1)$, but as per the graph if we assume $\Phi_1=2$ then $\widehat{c_i}=3, \forall i$

I do not quite get where I made the mistake.

Answer 1

You have caught an instance of the infamous off-by-one error in that popular textbook whose name we shall not mention again.

To repeat, it is correct that "the cost $c_1=1$, $\Phi_0=0$", "$num_1=size_1=1$ $\implies$ $\Phi_1 = 2\cdot1-1 =1$" and " $\hat{c_1}=$ $c_1+\Phi_1-\Phi_0$ $=2$". It is incorrect to state that $\widehat c_i=3$ for all $i$.

The first $\text{T}\scriptsize{\text{ABLE}}\small\text{-I}\scriptsize\text{NSERT}$ operation is indeed very special. It is not considered as an expansion, an event that is defined as "in which lines 5–9 are executed". However, it does not maintain $size_i = size_{i-1}$, either. So neither computation for $\widehat{c_i}$ in the textbook is fit for $\widehat{c_1}$.

That error is confusing given that we tend to trust fully an exemplary textbook where so much attention have been paid to detail and correctness.

On the other hand, that error is not very significant since, as you noted, it still holds that "the amortized cost is at most 3".

By the way, if you take a closer look at the figure at the end of question, it shows the potential at the end of first $\text{T}\scriptsize{\text{ABLE}}\small\text{-I}\scriptsize\text{NSERT}$ operation, $\Phi_1=1$, the correct value.