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$ :(

• Is $3n$ a too big bound or am I missing something?

• 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:

• $a(n)$ is the amortized value of the $n$th insertion

• $\phi(n)$ is the potential function

• $t(n)$ is the actual value the insertion is worth ($1$

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$

StackExchange Computer Science Q#82955, answer score: 3