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