Return to 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 \cdot 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 \cdot 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 \cdot 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 \cdot 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 \cdot 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 am made the mistake.

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.

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 \cdot 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 \cdot 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 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 am making the mistaken.

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 \cdot 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 \cdot 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 \cdot 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 \cdot 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 \cdot 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 am made the mistake.

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 \cdot 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 \cdot 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,

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 am making the mistaken.

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 \cdot 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 \cdot 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 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 am making the mistaken.