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
    @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
    Thanks @J.M. and thank you Zev!2011-09-28