Finding potential function for dynamic array

Question

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 3ドルn$ :(

1. Is 3ドルn$ 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 2ドルn$ isn't enough!! which makes me think 3ドルn$ 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

2ドルnd$ 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$?

• Raphael: "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: 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.

Answer 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$

Answer 2

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

• CIsForCookies: I'm pretty sure my proof is wrong. Can't explain how and why, though