3
$\begingroup$

The following problem is based on the section about dynamic table as part of the discussion about amortized analysis in CLRS

Problem: We are given a dynamic table $T$ that supports INSERT operation, implemented as an array and allows a constant amortized time per operation. Change the data structure so that when the array is full its size is increased by $\sqrt{T.size} $, i.e., the new size is $T.size +\sqrt{T.size}$.
Show, that the amortized time per operation is $ \Theta( \sqrt{n} ) $, in other-words, show that the total complexity that is needed for a sequence of $ n $ operations in the W.C. is $ \Theta(n\sqrt{n}) $.

Attempt: I really have no idea, I've been stuck on this problem for a few days and I would really appreciate a fat hint. Here's what I did though,
Consider the $i$-th INSERT operation,
If we insert an element and there is no expansion of the table then
$ T.size_{i} = T.size_{i-1} $ , $ T.num_i = T.num_{i-1} + 1 $ , $ c_i = 1 $.
If we insert an element and there is an expansion of the table then
$ T.size_{i} = T.size_{i-1} + \sqrt{T.size_{i-1}} $, $ T.num_i = T.num_{i-1} + 1 = T.size_{i-1} + 1 $ , $ c_i = i+1 = T.size_{i-1} + 1 $

Where $ c_i $ is the cost of the $i $-th operation. $ T.size_i $ is the size of the table at the $i $-th operation. $ T.num_i $ is the number of elements in the table at the $i $-th operation.

Let us look at a sequence of $n$ TABLE-INSERT operations on an initially empty table.

If the current table has room for the new item (or if this is the first operation), then $c_{i}=1$
If the current table is full, however, and an expansion occurs, then $c_{i}=i:$ the cost is 1 for the elementary insertion plus $i-1$ for the items that we must copy from the old table to the new table.

The total cost of $n$ TABLE-INSERT operations is therefore

$\sum_{i=1}^{n} c_{i} \leq n+ [ ( 1+ \sqrt{1} ) + ( ( 1+ \sqrt{1} ) + \sqrt{ 1+ \sqrt{1} } ) + ... ] $

[ Well, this is it, I'm stuck from here on ( I made a few more things on a draft paper which I don't think are worth writing, one of them is trying to solve the recurrence relation when the table expands $ T.size_{i} = T.size_{i-1} + \sqrt{T.size_{i-1}} $, whose solution won't be of any value ). the $n$ comes from $n$ elementary insertions into the table. My trouble is the expression $ [ ( 1+ \sqrt{1} ) + ( ( 1+ \sqrt{1} ) + \sqrt{ 1+ \sqrt{1} } ) + ... ] $ which comes from the table's expansion, I'm stuck at realizing how many times we add this sum and what it sums to, this is my main difficulty in the problem. ]

I understood the section about dynamic tables in the book and its analysis as it appears in the book when the table size grows at a constant factor of 2, but due to the nature of the problem above ( the table size does not grow constantly ), I'm having trouble wrapping my head around it.


I have some direction for the amortized analysis using accounting method ( but nevertheless, I'm supposed to find the worst-case tight bound for the sequence of operations for which without, my amortized analysis won't have a validation ):
In the moment of the expansion of the table, if the number of cells was $ k $ then $ \sqrt{k} $ cells will be added. For every element that I'll put into the table i'll buy $ \sqrt{k} + 2 $ coins, one coin will be used for insertion and the rest I put into the bank, such that for every inserted element into the $ \sqrt{k} $ cells, I keep $ \sqrt{k} + 1 $ coins. I fill $ \sqrt{k} $ cells and thus, in the bank, I have at the end of the filling process, $ \sqrt{k}\cdot (\sqrt{k}+1 ) = k + \sqrt{k} $ coins. ( Now I'll have to talk about how to take out the coins out of the bank at the moment of the expansion to pay for the expensive operation of expansion, but this explanation is the heart of the amortized analysis explanation ).

$\endgroup$
3
  • $\begingroup$ Are you sure the table size is multiplied by T.size + sqrt (T.size)? So you would go from size 100 to size 11,000? $\endgroup$
    – gnasher729
    May 12 at 22:41
  • $\begingroup$ Assuming you increase the table size by sqrt(T.size): How often do you resize to go from table size n to 2n? Each time you increase the size by an amount from sqrt(n) to sqrt(2n), so you need between n / sqrt(n) = sqrt(n) and n / sqrt(2n) = sqrt(n/2) increases. $\endgroup$
    – gnasher729
    May 12 at 22:44
  • $\begingroup$ @gnasher729 You're right, it's supposed to be " its size becomes $ T.size := T.size + \sqrt{T.size} $ ". I have no idea why I wrote "multiplied". I'm very sorry, my head was so wrapped up in the problem for these couple of days that my brain almost melted and was feeling as if I was almost about to get stroke. I'll edit. $\endgroup$ May 12 at 22:45

1 Answer 1

2
$\begingroup$

Assume $n\ge2022$. Consider a sequence of $n$ INSERTs.

Lower bound of time for $n$ INSERTs
Each expansion that has been done expands the capacity by no more than $\sqrt n$. So at least $n/\sqrt n=\sqrt n$ expansions has happened.

Consider the last $\frac{\sqrt n}2$ expansions. The earliest one of them happens when the number of elements is at least $n-\frac12\sqrt n\sqrt n=\frac n2$. So the total time-cost of these expansions is at least $(\frac n2+\sqrt{\frac n2})\cdot(\frac12\sqrt n)\ge\frac n4\sqrt n$.

Upper bound of time for $n$ INSERTs
Consider four consecutive expansions, assuming the first starts at size $k$. The first expansion increases the capacity by $\sqrt k$. The second expansion by $\sqrt{k+\sqrt k}$. The third by $\sqrt{k+\sqrt k +\sqrt{k+\sqrt k}}$. The fourth by $\sqrt{k+\sqrt k +\sqrt{k+\sqrt k}+\sqrt{k+\sqrt k +\sqrt{k+\sqrt k}}}\ge\sqrt k + 1$. So with every third expansion, the size of capacity increase increases by at least $(\sqrt k + 1)-\sqrt k=1$.

Hence the increase of capacity at $t$-th expansion is at least $t/3$. the total increase of capacity by the first $3t$ expansions is at least $3(1+2+\cdots+(t-1))=\frac{3(t-1)t}2$. On the other hand, the capacity is no more than $n+\sqrt n$ after $n$ INSERTs. Let $e$ be the number of expansions that happens during $n$ INSERTs. Then $$\frac{3(e/3-1)e/3}2 \ge n + \sqrt n,$$ which implies $e\le 6\sqrt n$.

Each expansion takes at most $n+\sqrt n$ time. so all expansions take at most $e(n+\sqrt n)\le 6n\sqrt n$ time. Including the time to assign $n$ values, which take $n$ time, the total time is at most $7n\sqrt n$.

So, the total time for $n$ INSERTs is $\Theta(n\sqrt n)$.
The reasoning above are sloppy here and there. To some people including myself, it might be considered as a proof that is good enough. To some people including myself, it may not be acceptable. Anyway, this answer should be good enough to be "a fat hint".

$\endgroup$
5
  • $\begingroup$ Thank you so much, but I'm very sorry, out of foolishness I wrote " multiplies " instead of " its size becomes $ T.size := T.size + \sqrt{T.size} $ ", I fixed my question, can you please re-answer it? $\endgroup$ May 12 at 22:47
  • $\begingroup$ Still, from what you wrote, I think I made some progress on the amortized analysis ( though, not on the general upper and lower bounds in W.C. for the sequence of $n$ operations ): I think if putting an element into a cell costs $ \sqrt{n} + 2 $ coins. We can pay one coin for filling the cell, and save $ \sqrt{n} + 1 $ coins as credit in the bank. At time $ t = 0 $, the size of the table is some initial $ k$ and we can put into it $ k $ elements, s.t. the accumulated budget is $ k(\sqrt{n} + 1) $, enough to finance copying of $ k $ elements into new array. $\endgroup$ May 12 at 22:57
  • $\begingroup$ In the next expansions of the table, notice that if the size of the table immediately after an expansion is $ k + \sqrt{k} $, the newly inserted elements accumulate a budget of $ k + \sqrt{k} \leq \sqrt{k} \cdot ( \sqrt{n} + 1 ) $ and that allows us to copy the $ k + \sqrt{k} $ existing elements "freely". in total, we used $ n\cdot (\sqrt{n} + 2 ) = O(n\sqrt{n}) $ coins. $\endgroup$ May 12 at 22:57
  • 1
    $\begingroup$ @hazelnut_116 it looks like you are on the right direction. In fact, because of the so much leeway allowed by the hidden constant factor in $\Theta()$, we can consider the expansion of the size from something like $n/9$ to $n$, computing a coarse estimate of the lower bound and upper bound of the cost needed. $\endgroup$
    – John L.
    May 12 at 23:24
  • $\begingroup$ A key idea is to show the number of expansions during the first $n$ INSERTs is $O(\sqrt n)$. $\endgroup$
    – John L.
    May 13 at 6:34

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.