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

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.