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

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

$\endgroup$
  • $\begingroup$ can anyone please help me? If any modification is required pls do say me, if the question is not clear... $\endgroup$ – Abhishek Ghosh Jul 10 '20 at 15:19
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$
  • 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$ – Abhishek Ghosh Jul 12 '20 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 '20 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$ – Abhishek Ghosh Jul 12 '20 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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