1
$\begingroup$

The question (in a nutshell) is this. I have an array which is an implementation of a stack. The array starts off with a size of 4 and every time it overflows (the user pushes a value when the array is full), a new array of size N + 4 is created and the old values are pushed in to the new array.m Every time the user pushes a value which creates a new array, this is called a special push.

I'm looking for a way to express the cost (in pushes) of the i th special push.


I made a table showing the number of the special push (i) and the amount of pushes they cost respectively:

1 1
2 5
3 9
4 13
5 17
6 21
7 25
8 29

Basically, I need to find a relation between the first column and the second. If I subtract the value in the second column with the value in the first I get that the differences start at 0 and increment by 3 each time. Therefore I have:

$$ x - i = 0,3,6,9,12,15,... $$

Where x is the cost of the ith special push.

How can I express this? Am I over-complicating things?

  • 0
    If this is an implementation detail of an actual program (as opposed to a homework problem), if the stack grows very often, you might consider increasing the size by a constant factor instead of by 4.2011-09-28
  • 0
    @marty yeah it's a constraint. If I was programming this I would probably increase it by much more than 4 :)2011-09-28

1 Answers 1

3

It appears that the formula you want is $$f(i)=4i-3$$ where $i$ is the number on the left.

I don't really know anything about what a stack is, but working from your description, this formula can be seen to be correct because it is correct for $i=1$, and then every time $i$ is increased to $i+1$, the size of the corresponding value should be increased by 4, which is captured by $$f(i+1)=4(i+1)-3=(4i-3)+4=f(i)+4$$

  • 0
    As for why this is plausible: note that if you take successive differences of the original data, you get a constant difference of 4 (i.e. the the $n$-th term is always four more than the one before it); the $-3$ part you can get by figuring out what value of $k$ in $4n+k$ is needed so that the expression is equal to $1$ for $n=1$.2011-09-28
  • 0
    Thanks @J.M. and thank you Zev!2011-09-28