# Finding potential function for dynamic array

About dynamic array, doubling it's size with every element that is beying its limit:

From what I understand, the number of operations between the $n$th element and the $n+1$th depending on if $n+1$ is $2^k + 1$ (for some $k \in \mathbb{N}$).

If so, we need to allocate a new array and copy the last n elements + the new element. From what I see, if I define a potential function $\phi(n)$ then it should be $\phi(n+1) = \phi(n/2) + n/2 + 1$

Explanation: $\phi(n/2)$ is the last time we expanded the array, $n/2$ are the next elements that were inserted to only one (the last) array, and $1$ is the current element.

However, from what I saw (wikipedia) the actual function is $\phi(n) = 2n - N$ where $n$ is number of elements and $N$ is array length.

Either way, $\phi(n) \le 2n$, and my HW assignment was to show it is bounded by $3n$ :(

1. Is $3n$ a too big bound or am I missing something?
2. Is the $\phi$ equal to the one wiki has (I can't see how...)? how do they differ

EDIT: I now have a new notion about the answer - using the bank / accounting method. My initial array has size of 2. The assignment is to show that paying 3 for each insertion will ensure I'm never in "overdraw". I know that if I only pay 2 for each insertion, then when I insert the first 2 elements, I paid 4 and used only 2, when I insert the 3rd, I use 3 and pay only 2 (so I use 1 from the bank, which leaves only 1 there). In the 4th insertion I'll add another 1 to the bank, but in the 5th insertion I'll have to overdraw!

So, clearly $2n$ isn't enough!! which makes me think $3n$ will do.

I know what I added here might contradict my first notion, and I don't understand to actually answer this. Any help will be appreciated. Thanks

$2nd$ EDIT:

The HW assignment is to show a specific $\phi(n)$ so that $a(n) = t(n) + \phi(n) - \phi(n-1)$, where:

1. $a(n)$ is the amortized value of the $n$th insertion
2. $\phi(n)$ is the potential function
3. $t(n)$ is the actual value the insertion is worth ($1$ or $n+1$)

It's easy to see that, using the Wikipedia function ($\phi(n) = 2n - m$ [m is the array's size]$)$, if $t(n) == 1$ then $a(n) = t(n) + \phi(n) - \phi(n-1)$ is actually $a(n) = 1 + [(2n - m) - (2(n-1) - m)]$ which is $1 + 2 = 3$. But what about when $t(n) = n+1$?

• "However, from what I saw (wikipedia) the actual function is ϕ(n)=2n−N" -- there is no single correct function here. Anything goes, and there are usually many that work. The quality of the bound may depend on your choice, though. Oct 25, 2017 at 9:54
• Please don't just append edits. SE keeps a revision history for you; the question should be the best, cohesive form you can come up with at any point in time. Oct 25, 2017 at 21:37

## 2 Answers

When $$t(n)=n+1$$ it's the case when the array is full and we need to double the size of our array, so:

As you mentioned our potential function is $$\phi(n) = 2n - m$$, but now the array size doubled, thus $$m = 2n$$ and that means that $$\phi(n) = 0$$.

Our potential function for the before state is $$\phi(n-1) = 2(n-1)-m$$, and $$m=n$$ (because the array is full), thus $$\phi(n-1) = 2(n-1)-n = n-2$$.

And the final result is: $$a(n)=t(n)+\phi(n)-\phi(n-1)=n+1+0-(n-2)=n+1-n+2=1+2=3$$

You've already proved it! You said you were meant to bound it by $3n$ and you've bound it by $2n$. Well, $2n \leq 3n$, right?

• I'm pretty sure my proof is wrong. Can't explain how and why, though Oct 26, 2017 at 10:05