$\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


The following is the section from Introduction to Algorithms by Cormen. et. al. in the Dynamic Tables section.

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-table$ with $ 2 • size[T]$ slots}$

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

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

$ 8\quad\quad\quad table[T] \leftarrow new-table$

$ 9\quad\quad\quad size[T] \leftarrow 2 • 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.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 . 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.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,

Plot

The text represents graphically the $ \Phi_1=2$ which sort of contracts $ (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 am making the fault.