3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ "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. $\endgroup$ – Raphael Oct 25 '17 at 9:54
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Oct 25 '17 at 21:37
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I'm pretty sure my proof is wrong. Can't explain how and why, though $\endgroup$ – CIsForCookies Oct 26 '17 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.