# 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. – Raphael Oct 25 '17 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. – Raphael Oct 25 '17 at 21:37

## 1 Answer

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 – CIsForCookies Oct 26 '17 at 10:05