I was given the following homework question:

Implement an extendable table using arrays that can increase in size as elements are added. Perform an experimental analysis of each of the running times for performing a sequence of n add methods, assuming the array size is increased from N to the following possible values:

  • 2N
  • N + ceiling(√N)
  • N + ceiling(log N)
  • N + 100

I'm just a little confused about what this question is asking, and was hoping for some help/clarification. The way I understand it, you could implement something like this in Python with a two-dimensional array (the "extendable table"), and then append varying numbers of values for each scenario. Am I understanding the implementation correctly?

Then, I'm also a bit unclear on what number of values you'd be appending. Would you literally first test it with say, 16 values, then 32 (2N), then 20 (ceiling(√N)), etc? Or is it more complex than that? Any help is appreciated!


closed as off-topic by D.W., Luke Mathieson, J.-E. Pin, David Richerby, Juho Oct 30 '13 at 10:04

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about computer science, within the scope defined in the help center." – D.W., Luke Mathieson, J.-E. Pin, David Richerby, Juho
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ If you want to understand what your instructor wants you to do, you should ask your instructor, not us here. $\endgroup$ – D.W. Oct 15 '13 at 16:23

An extendable array isn't a two-dimensional array (I don't know what's an extendible table). The idea is that you start with an array of a fixed size, and each time you are trying to insert an element into the array but it's full, you increase the size from $N$ (its current size) to $f(N)$ (its subsequent size, until it needs to be enlarged again). That means that you allocate new memory ($f(N)$ items), copy the old array into the new place, and then free the old memory. When you have added $f(N)-N-1$ more elements, a subsequent insertion would require enlarging the array to size $f(f(N))$, and so on. The question is what is the best choice for the function $f$.

Experimentally, you can try different functions $f$. For each such suggestion $f$ (and the same initial size of the array, say something like 20 or 100, you decide), plot $n$ against the time it takes to add $n$ elements (what elements you add isn't important; you could just add zeroes), averaged over several trials. I'll let you decide how exactly to do that, but you probably want several different values of $n$, and $n$ as large as roughly a million or so (you decide exactly how large). You can then find which function is better than others. I suggest you use C rather than python in your experiments.


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