2
$\begingroup$

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,

Plot

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.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Once again. A great thanks for your help and guidance. And about the off-by-one error/ typo as you pointed out (which does not affect the correctness of formulae) was also encountered by me and I tired to convince myself that it does not affect the correctness of the formulae (as you said) using a bit of mathematics here : math.stackexchange.com/questions/3751463/… $\endgroup$ Jul 12, 2020 at 6:44
  • 1
    $\begingroup$ Sorry, in fact the case about $\lg n$ is not an off-by-one error/typo since "≤" instead of "=" is used to connect the quantities. $\endgroup$
    – John L.
    Jul 12, 2020 at 12:23
  • 1
    $\begingroup$ if you take a closer look at the figure at the end of question, it shows the potential at the end of first TABLE-INSERT operation, $Φ_1=1$, the correct value. Thanks for this help again and here is what I found : drive.google.com/file/d/1-wHAE-GvrUMkUNPQ96LfNeysQB-076_N/… $\endgroup$ Jul 12, 2020 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.