2
$\begingroup$

I'm trying to prove that the amortized time complexity of appending to a dynamic array that resizes in accordance with capacity = $N$ to $N+\lceil{\frac{N}{4}}\rceil$ is $O(1)$. I'm assuming that resizing an array from $x$ to $y$ "costs" $y-x$ primitive operations.

Here is my reasoning so far. Assume that an array is full when it has a capacity $k$. Upon the next append call, the array resizes to $k+\lceil{\frac{k}{4}}\rceil$. Thus there are $\lceil{\frac{k}{4}}\rceil$ new cells in which elements can be appended to. This array will be full when all new $\lceil{\frac{k}{4}}\rceil$ cells are filled. After this takes place, another resize event will have to occur. This resize event changes the capacity as follows: $$k+\left\lceil{\frac{k}{4}}\right\rceil \to \bigg(k+\left\lceil{\frac{k}{4}}\right\rceil\bigg) + \left\lceil{\frac{k+\lceil{\frac{k}{4}}\rceil}{4}}\right\rceil$$

So, in the $\lceil{\frac{k}{4}}\rceil$ between resizing events, we need to "save" up primitive operations. For append to $O(1)$, we need to "save" a constant real number $b$ of primitive operations per cell, i.e. $b$ must not depend on $k$. Mathematically, we want to show: $$\exists b \in\mathbb{N}\; s.t. \; \forall k\in\mathbb{N}, \;\; b\left\lceil{\frac{k}{4}}\right\rceil\ge \left\lceil{\frac{k+\lceil{\frac{k}{4}}\rceil}{4}}\right\rceil $$

We note a couple of things. Firstly, $\lceil{x}\rceil = x+\theta$ for some $\theta\in [0,1)$. Secondly, $b$ and the ceilings in the above inequality are all positive, so the inequality holds:

$$\iff b\bigg(\frac{k}{4}+\theta_1\bigg)\ge \frac{k+\frac{k}{4}+\theta_1}{4}+\theta_2$$ $$\iff bk + 4b\theta_1 \ge \frac{5k}{4}+\theta_1 +4\theta_2$$ $$\iff b \ge \frac{1}{k}\bigg(\theta_1-4b\theta_1+4\theta_2\bigg)+ \frac{5}{4}$$

The problem I have is this suggests that $b$ need not be that large at all, some I'm pretty sure I've done something wrong intuitively.

$\endgroup$
2
  • $\begingroup$ Size always changes from N to some value ≥ 5/4 N. $\endgroup$
    – gnasher729
    Commented Apr 4, 2017 at 19:53
  • $\begingroup$ I don't see how this implies O(1) for append. Sorry if this is trivial. $\endgroup$ Commented Apr 4, 2017 at 23:30

0

Your Answer

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