patternMinor
Amortized analysis on a dynamic table that grows its size by $\sqrt{size} $
Viewed 0 times
growssizeanalysissqrtitsthatdynamicamortizedtable
Problem
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 o
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 o
Solution
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".
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".
Context
StackExchange Computer Science Q#151490, answer score: 2
Revisions (0)
No revisions yet.